Solution of an equation by repeated substitution

[Liv]

I think that all equations f(x) = 0 can be re-written as x = g(x).

If x0 is a root (unknown) and x01 some approximation of the root, sometimes we can obtain a better approximation of the root by repeated substitution, such as :

x02 = g(x01), where x02 is closer to x0 than x01 ;

x03 = g(x02) or = g(g(x01), where x03 is closer to x0 than x02.

Is that true for any function f (or g) ? Does someone know the proof or a book with it ?

Probably the answer is obvious ... .

I saw something about in an old book of algebra with polynomials, but I find it no more...

Thank you ! Liv.

[RichardJ]

I think that all equations f(x) = 0 can be re-written as x = g(x).

This is certainly true. It just means g(x)=f(x)+x

If x0 is a root (unknown) and x01 some approximation of the root, sometimes we can obtain a better approximation of the root by repeated substitution, such as :

x02 = g(x01), where x02 is closer to x0 than x01 ;

x03 = g(x02) or = g(g(x01), where x03 is closer to x0 than x02.

I would be surprised if this were not true "sometimes".

Is that true for any function f (or g) ?

No. Take f(x)=x^2-1, which has roots at x=1 and x=-1. We would then have g(x)=x^2+x-1. Take a guess of x=2 for the root, then g(x)=5, which is further from the root than the guess.

[Liv]

Sorry, Richard, incomplete question !

I forgot to write that : f(x) = c*ln(a + b*x) - x and obviously g(x) = c*ln(a+b*x), x > 0, with, let's say, both a & b > 0 and c < 0.

I tried something with Taylor series for ln(a + b*x) or Newton method for finding roots, but for the moment I can't see the proof.

I know c*ln(a + b*x) - x = 0 can be solved with the aid of Lambert function, but this can help me ... ?

Regards, Liv.

[RichardJ]

Let a=1, b=1, c=-1. Guess the root at 4, then g(4)=-1.0609. Then g(-1.0609)=0.4952-PI*i (i.e. a complex result). So it seems your conjecture is not correct.

[Liv]

I think that a necessary condition is for g(x) to be monotonic around x0, whatever the form of g(x) ...

Indeed my specific equation ln(a + b x) = x cannot be true for any values of a, b, c. Some tighter ranges for these parameters may be :

0 < a < 1, 0 < b < 1, -1 < c < 0 , with for ex. a = 10^-3 , b = 0.1, c = -0.5 ; a = 10^-4, b = 0.01, c = -0.6, and so on. In the attached worksheet a = 10^-3, b = 0.1 and c = -0.85. For such values the eq has a real root and the repeated substitution approaches the root ...

So in the particular case of my g(x) := ln (a + b x) I was wondering if there's some condition for a, b, c in order to have a real root and to make my repeated substitution a convergent process to the root.

And particularly, for some given values for a, b and c (for which equation g(x) + x = 0 has real root) are there some bounds for the starting value (x01 in attached Mcd15 file) which guarantee convergence to the root ?

Regards, Liv.

[RichardJ]

Sorry, but trying to prove (or disprove) your conjecture is way beyond my mathematical capabilities. Up to this point I have shown that your conjecture is not correct over a wide domain by simply by finding an example where it fails. But I have no idea how to determine the domain over which it is correct.