Dit is een onderwerp van de numerieke wiskunde. Bekend is dat de Newton-Raphson methode een 2eorde convergentie is. D.w.z. voor elke opeenvolgende waarde van het gezochte nulpunt levert dit een kwadratische snelheid op van de foutschatting. Dit is vrij gemakkelijk aan te tonen / te bewijzen. Want de f'(x) moet niet nul zijn en de f(x) juist wel als voor x het gezochte nulpunt ingevuld wordt. Abstract kun je dit vrij eenvoudig bewijzen door met de iteratiefunctie te gaan werken en deze f'(x) in te vullen op de Newton-Raphson manier. Nu is verder bekend dat je een gezocht nulpunt ook kunt bepalen met de koorden-Newton manier. Hierbij is de hulpfunctie / iteratiefunctie : An+1=An-((An-1-An)/(f(An-1-f(An))*f(An) met f als functie waarbij je nulpunt wilt hebben. Hierbij wordt gezegd dat deze van convergentiesnelheid (±)1,62 is. Je kunt dit wel zelf nagaan met een gemakkelijke functie en proberen hoe snel het gaat, of zelfs uitschrijven. Uiteindelijk zou je iets krijgen met: (x = precieze nulpunt) ln ((An+1-x)/(An-x))/ln((An-x)/An-1-x)) = ±1,62 Maar je moet dit getal toch ook kunnen bewijzen? Ik kom er niet uit. Kan iemand me helpen met dit te bewijzen? Alvast bedankt!
Franci
Student hbo - woensdag 19 mei 2004
Antwoord
Hoi Francis,
het door jou gevraagde bewijs heeft mij ertoe gezet om een gezellige combinatie van verschillende stukjes wiskunde te maken. De rij van Fibonacci blijkt hier namelijk ook van belang te zijn! Zelf betrek je er al het bewijs voor Newton-Raphson bij. Ik zal dat hieronder herhalen om de analogie met het bewijs voor Koorden-Newton duidelijk naar voren te laten komen. Overigens ga ik er express met vrij grote stappen doorheen om het een beetje compact te houden. Probeer zelf de tussenstappen na te gaan. Als je ergens niet uitkomt kun je natuurlijk altijd om meer informatie vragen.
Eerste deel voor Newton-Raphson: Gegeven: - de functie f:$\mathbf{R}$$\to$$\mathbf{R}$:r$\to$f(r), minstens 2 keer differentieerbaar. - een nulpunt x$\in$$\mathbf{R}$ waarvoor dus f(x)=0 en bovendien f'(x)$\ne$0 en ook f''(x)$\ne$0 (anders is de convergentie namelijk nog sneller). Definitie: - De Newton-Raphson-rij Rn+1 = Rn - f(Rn)/f'(Rn) Aanname/Gegeven: - We beginnen de rij met R0 in het juiste convergentie-gebied, zodat Rn convergeert naar x. (ik wil hier niet gaan bewijzen dat er inderdaad een gebied om x is waarop Newton-Raphson convergeert naar x) Te bewijzen: limn$\to$$\infty$ ln(Rn+1-x) / ln(Rn-x) = 2. Bewijs: We schrijven de Taylor-ontwikkeling voor f(r) rond het nulpunt x: f(r) = 0 + f'(x)·(r-x) + 1/2 f''(x)·(r-x)2 + hot, waarbij hot een afkorting is voor 'hogere orde termen'. Voor de afgeleide f'(r) hebben we: f'(r) = f'(x) + f''(x)·(r-x) + hot. Als we dit invullen met r = Rn dan vinden we f(Rn)/f'(Rn) = (f'(x)·(Rn-x) + 1/2 f''(x)·(Rn-x)2 + hot) / (f'(x) + f''(x)·(Rn-x) + hot) = (Rn-x) · (1 + 1/2 f''(x)/f'(x) · (Rn-x) + hot) / (1 + f''(x)/f'(x) · (Rn-x) + hot) = (Rn-x) · (1 - 1/2 f''(x)/f'(x) · (Rn-x) + hot) en dus Rn+1-x = Rn-x - f(Rn)/f'(Rn) = 1/2 f''(x)/f'(x) · (Rn-x)2 + hot oftewel ln(Rn+1-x) = ln(1/2 f''(x)/f'(x)) + 2·ln(Rn-x). Omdat ln(Rn-x)$\to$-$\infty$ voor n$\to$$\infty$ volgt hieruit de gevraagde limiet.
Tweede deel voor Newton-Raphson: Om de door jou genoemde definitie van de convergentie-orde te bereiken laat ik even zien dat die hieruit volgt via het volgende Lemma: Gegeven: - rij Xn met limn$\to$$\infty$ ln(Xn+1) / ln(Xn) = $\alpha$ Te bewijzen: - limn$\to$$\infty$ ln(Xn+1/Xn) / ln(Xn/Xn-1) = $\alpha$ Bewijs: Eigenlijk is dit gewoon een kwestie van herschrijven. We vinden dan namelijk dat ln(Xn+1/Xn) / ln(Xn/Xn-1) = ( ln(Xn+1) - ln(Xn) ) / ( ln(Xn) - ln(Xn-1) ) = ( ln(Xn+1)/ln(Xn) - 1 ) / ( 1 - ln(Xn-1)/ln(Xn) ) $\to$ ($\alpha$-1)/(1-1/$\alpha$) = $\alpha$. Overigens is dit bewijs overigens niet volledig als $\alpha$=0, dan moet je het net even iets anders formuleren.
Dan nu voor Koorden-Newton: Gegeven: - de functie f:$\mathbf{R}$$\to$$\mathbf{R}$:r$\to$f(r), minstens 2 keer differentieerbaar. - een nulpunt x$\in$$\mathbf{R}$ waarvoor dus f(x)=0 en bovendien f'(x)$\ne$0 en ook f''(x)$\ne$0 (anders is de convergentie namelijk sneller). Definitie: - De Koorden-Newton-rij An+1 = An - f(An) · (An-1 - An) / (f(An-1) - f(An)) Aanname/Gegeven: - We beginnen de rij met A0 in het juiste convergentie-gebied, zodat An convergeert naar x. (ook hier wil ik niet gaan bewijzen dat er inderdaad een gebied om x is waarop Koorden-Newton convergeert naar x) Gevraagd: limn$\to$$\infty$ ln(An+1-x) / ln(An-x). Welnu: De Taylor-ontwikkeling voor f(r) rond het nulpunt x kunnen we nu invullen voor r = An en r = An-1: f(An-1) = f'(x)·(An-1-x) + 1/2 f''(x)·(An-1-x)2 + hot, en f(An) = f'(x)·(An-x) + 1/2 f''(x)·(An-x)2 + hot. Dit invullen in de recursie-vergelijking voor Koorden-Newton levert f(An) · (An-1 - An) / (f(An-1) - f(An)) = ((An-1-x) - (An-x)) · (f'(x)·(An-x) + 1/2 f''(x)·(An-x)2 + hot) / (f'(x)·((An-1-x)-(An-x)) + 1/2 f''(x)·((An-1-x)2-(An-x)2) + hot) = (An-x) · (1 + 1/2 f''(x)/f'(x)·(An-x) + hot) / (1 + 1/2 f''(x)/f'(x)·((An-1-x)+(An-x)) + hot) = (An-x) · (1 - 1/2 f''(x)/f'(x)·(An-1-x) + hot) en dus An+1-x = An-x - f(An) · (An-1 - An) / ( f(An-1) - f(An) ) = 1/2 f''(x)/f'(x) · (An-x)(An-1-x) oftewel ln(An+1-x) = ln(1/2 f''(x)/f'(x)) + ln(An-x) + ln(An-1-x). Omdat ln(An-x)$\to$-$\infty$ voor n$\to$$\infty$ wordt de term ln(1/2 f''(x)/f'(x)) steeds meer verwaarloosbaar en gaat de rij ln(An-x) zich steeds meer gedragen als de rij van Fibonacci!! Maar dan weten we wat de limiet van ln(An+1-x) / ln(An-x) zal zijn, kijk maar op Rij van Fibonacci en Gulden Snede. De gevraagde convergentie-orde is dus gelijk aan de gulden snede F = =(1+√5)/2 = 1.61803398874.... Gebruik tenslotte het lemma om aan jouw definitie van de convergentie-orde te komen...
Ik hoop dat je het net zo leuk vindt als ik om hier de gulden snede weer tegen te komen. Met vriendelijke groet,
