4.3 Algoritmul lui Overholt

Fie sirul de numere reale (xn)n convergent la x, cu propietatea:

xn+1 − x =∑k≥1

ak(xn − x)k, (4.59)

unde a1 6= 1Daca a1 = a2 = . . . = ap−1 = 0, iar ap 6= 0, atunci p este ordinul de

convergenta al sirului (xn)n. Deci:

xn+1 − x = O((xn − x)p) (4.60)

In acest caz xn+1 se numeste aproximatie de ordinul p a numarului x.Algoritmul lui Overholt transforma un sir (xn)n pentru care avem dez-

voltarea 4.59, ın siruri cu ordine din ce ın ce mai mari pentru limita sa x.Descriem ın continuare pe scurt acest algoritm.Pentru detalii privind al-

goritmul lui Overholt recomandam cititorului [9],[12] si [64].In finalul acestui paragraf prezentam o metoda iterativa cu ordin de

convergenta oarecare K pentru rezolvarea ecuatiei x = f(x). Pentru aceastase combina metoda aproximatiilor succesive cu algoritmul lui Overholt.

Fie asadar (xn)n un sir de numere reale convergent la x, sir pentru careavem dezvoltarea 4.59, si dn = xn − x, n = 0, 1, 2 . . . Din 4.59 rezulta:

xn+1 = x + a1dn + a2d2n + . . .

De aici, deoarece xn = x + dn, obtinem:

xn+1 − a1xn

1− a1= x +

a21− a1

d2n + . . .

Deci xn+1−a1xn

1−a1este o aproximatie de ordinul doi pentru x.

Deoarece a1 ın general nu este un numar cunoscut, vom cauta o aproximatiea acestuia a1. Fie:

a1 =xn+2 − xn+1

xn+1 − xn

Folosind dezvoltarea 4.59 obtinem succesiv:

1

a1 =(x + a1dn+1 + a2d

2n+2 + . . .)− (x + a1dn + a2d

2n + . . .)

x + dn+1 − (x + dn)

= a1 + a2(dn+1 + dn) + . . . = a1 + a2((a1dn + a2d2n + . . .) + dn) + . . .

Rezulta:

a1 = a1 + (1 + a1)a2dn + . . .

(4.61)

2