3

I need to solve a non linear equation of this kind:

$$f(x) = x$$

where $f(x)$ is an injective function

I can't isolate $x$ so I want to use an iterative method in order to find the value of $x$.

In a naive way I used this strategy:

$x_0 = 1$ random initial value

$x_1 = \frac{(f(x_0)+x_0)}2$

$x_2 = \frac{(f(x_1)+x_1)}2$

and so on...

$x_n$ converge and I got the right result, but i'm unable to find the name of this method. So did you know the name of this method ? And what is the most efficient iterative method in this case ? ($f(x)$ is a hard to derive function)

EDIT

For the people who asked, in my particular case I need to determined $h$ (the water level) from the manning formula.

$$\frac{Q}{k*\left(\frac{\frac{h^2}{p}+b*h}{b+2*h*\sqrt{1+\frac{h^2}{p^2}}}\right)^\frac{2}{3}*\sqrt{J}*\left(b+\frac{h}{p}\right)*h} = h$$

And

Q   = 1.2/1000 
k   = 20
b   = 0.1 
J   = 0.007
p   = 2/3
obchardon
  • 257
  • 2
    It is a type of fixed point iteration with no particular name. If f is a scalar function then the secant method will be faster than yours. – Ian Aug 10 '17 at 22:12
  • See also http://math.usm.edu/lambers/mat460/fall09/lecture13.pdf for the Steffenson method which is a restarted Aitken iteration or an approxomation to Newton`s method, which means that convergence, if it happens, is fast. – Lutz Lehmann Aug 10 '17 at 22:49
  • 1
    I think including your test functions and initial guesses would make for an interesting update/addition. Especially, if your iteration converges and the "standard" iteration does not. – Carl Christian Aug 11 '17 at 06:28

5 Answers5

3

You have discovered a variant of the standard functional iteration or fixed point iteration. The standard iteration is $$x_{n+1} = f(x_n).$$ You are using $$x_{n+1} = g(x_n),$$ where $$g(x) = (x + f(x))/2.$$


EDIT: A recent question and its answer by @Lutz started a thought process which prompted my decision to revise this answer thoroughly. Briefly, it is possible to construct functional iterations which converge at least quadratically without recomputing derivatives as required for Newton's method. However, since it is necessary to evaluate the derivative at the fixed point, this technique is mostly limit to the construction of good problems for students.

Let $I \subset \mathbb{R}$. A function $h : I \rightarrow I$ is a contraction, if there exists $L \in [0,1)$, such that $$\forall x, y \: : \: |h(x) - h(y)| \leq L | x-y|$$ If $I$ is compact and if $h : I \rightarrow I$ is a contraction, then $h$ has precisely one fixed point $z \in I$ and the functional iteration $$ x_{n+1} = h(x_n)$$ converges to $z$ for any starting value $x_0 \in I$.

If $I = [a,b]$ and $h \in C^1(I)$ has a fixed point $z \in [a,b]$ and $|h'(z)| < 1$, then there exists compact interval $J \subseteq I$ such that the restriction of $h$ to $J$ is a contraction. This follows from the mean value theorem and the continuity of $h'$.

We can exploit the above mentioned property to design functional iterations which are convergent. Suppose $f$ has a fixed point $z$, but $|f'(z)|>1$. Then as stated by @Ian, the iteration driven by $f$ will not converge to $z$, but the function $g$ given by $$g(x) = \frac{f(x)-f'(z)x}{1-f'(z)}$$ satisfies $$ g(z) = \frac{f(z)-f'(z)z}{1-f'(z)} = \frac{z-f'(z)z}{1-f'(z)} = \frac{1-f'(z)}{1-f'(z)}z= z$$ and $$ g'(x) = \frac{f'(x)-f'(z)}{1-f'(z)} \quad \Rightarrow \quad g'(z) = 0.$$ It follows that the functional iteration driven by $g$ will converge at least quadratically to $z$. In practice, it is not realistic to assume that the exact value of $f'(z)$ is available, but we can have linear convergence if we know a good approximation. Specifically, suppose $c \approx f'(z)$ and $c \not = 1$. Then we consider the function $h$ given by $$h(x) = \frac{f(x)-cx}{1-c}.$$ As before, we have $$h(z) = z$$ and $$h'(x) = \frac{f'(x)-c}{1-c}$$ which implies $$h'(z) = \frac{f'(z)-c}{1-c}.$$ Therefore, $|h'(z)| < 1$ provided that $|f'(z)-c| < |1-c|$.

The aforementioned question by @UmShmum is provides an excellent test case for these ideas. Consider the non-linear equation $x = f(x)$ where $$f(x) = 2 \sin(x).$$ It is clear that $z=0$ is a fixed point of $f$, but since $f'(x) = 2 \cos(x)$ implies $f'(0) = 2$, the standard functional iteration will not converge. However, if $g$ is given by $$g(x) = \frac{f(x)-f'(0)x}{1-f'(0)} = 2(x-\sin(x)),$$ then $g(0) = 0$ and $g'(x)=2(1-\cos(x)$ implies $g'(x) = 0$. It follows that the functional iteration given by $g$ will converge at least quadratically to $0$. In fact, the convergence will be cubic, because $g''(x) = 2 \sin(x)$ implies $g''(0) = 0$.


The primary use of this technique is to construct problems which will allow students to apply the definition of stable/unstable fixed points and study the convergence of functional iterations. The need to evaluate the derivative at the fix point significantly reduces the practical utility of this technique. If we cannot evaluate the derivative, then we might as well use the hybrid method obtained by combining bisection with the secant method to achieve ensure convergence which is ultimately superlinear.
Carl Christian
  • 12,583
  • 1
  • 14
  • 37
  • Interesting, if I use the standard fixed point method, my iteration diverge. I just implement the secant method and indeed it is faster. – obchardon Aug 10 '17 at 22:35
  • 2
    The standard fixed point iteration diverges even upon good guesses if $|f'|>1$ at the root. The one in the OP diverges if $|f'+1|>2$ at the root. This is more likely to converge at all but sometimes converges slower than the standard iteration. – Ian Aug 10 '17 at 22:49
  • @Lutz You comments/answer prompted the revision of my answer to this question. I now have a new engine for good problems and I thought that it might prove useful to you. – Carl Christian Jan 19 '19 at 17:42
  • @Ian A recent question/answer by another user caused me to revisit this question and revise the answer. I now have a new engine for good problems and I thought that it might prove useful to you. – Carl Christian Jan 19 '19 at 17:46
2

As previously mentioned, this is the fixed point method. Of notable interest, you can make it converge faster if you use:

$$x_{n+1}=x_n-\frac{f(x_n)-x}{f'(x_n)-1}$$

Which is the special case known as Newton's method. The idea is simple, and its basically Euler's method for approximating differential equations in reverse. The approach is to take a function $g$ and a point $x_0$, and you want to solve $g(x)=0$, in this case, $g(x)=f(x)-x$. To do this, take the tangent at $x_0$ and solve for $x$ when $y=0$. This is $x_1$, and draw the tangent from $(x_1,g(x_1))$ and repeat the process.

This method generally converges much more quickly than the plain old fixed point method.

1

The fixed point iterative method

Your equation $f (x)=x $ is written as

$$x=\frac {f (x)+x}{2}=g (x) $$

you perform the recursive sequence $(x_n) $ by $$x_{n+1}=g (x_n) $$ with $x_1$ well chosen.

under some conditions $(|g'(x)|\le K <1) $, the sequence $(x_n) $ will converge to the solution of the equation $x=g (x) $ which is equivalent to $f (x)=x $.

0

Your function looks like $$ Q=h^{1+1+2/3}g(h),\ g(h)=k·\frac{\left(b+\frac hp\right)^{5/3}}{\left(b+2h·\sqrt{1+\frac{h^2}{p^2}}\right)^{2/3}}·\sqrt{J} $$ with $g(0)\ne 0$, so that a better fixed-point function would be $$ h=\left(\frac{Q}{g(h)}\right)^{3/8} $$

def g(h): return k*(b+h/p)**(5.0/3)/(b+2*h*(1+h**2/p**2)**0.5)**(2.0/3)*J**0.5
def f(h): return (Q/g(h))**(3.0/8)
h=1.0
for m in range(25): print "%2d  %.17f"%(m,h); h=f(h);

and indeed one gets some slow linear convergence

 0  1.00000000000000000
 1  0.06846822261190984
 2  0.12532902210311411
 3  0.11125221655251381
 4  0.11417470616134512
 5  0.11354304722719301
 6  0.11367841477714605
 7  0.11364935163434822
 8  0.11365558898031920
 9  0.11365425024800935
10  0.11365453757722653
11  0.11365447590813900
12  0.11365448914408215
13  0.11365448630327113
14  0.11365448691299022
15  0.11365448678212708
16  0.11365448681021405
17  0.11365448680418581
18  0.11365448680547963
19  0.11365448680520195
20  0.11365448680526152
21  0.11365448680524876
22  0.11365448680525150
23  0.11365448680525092
24  0.11365448680525103

Using the Steffenson/Aitken method

for m in range(25): print "%2d  %.17f"%(m,h); h1=f(h); h2=f(h1); h=h-(h1-h)**2/(h-2*h1+h2)

one gets to numerical stationarity in 5 steps with 10 function evaluations

 0  1.00000000000000000
 1  0.12205790231285119
 2  0.11366388839764867
 3  0.11365448681764546
 4  0.11365448680525102
 5  0.11365448680525100

in the next step the denominator is zero.

Lutz Lehmann
  • 126,666
  • I do not know why but I get a result which is slightly different from your. Would you accept to confirm ? Thanks. – Claude Leibovici Aug 17 '17 at 08:44
  • @ClaudeLeibovici : I copied the constants directly from the question, correcting the integer division in p, the code is exactly the one above. I get the same value $h_0=0.15698235371520258$ in f(0.0) and the final h is (numerically) the fixed point. I see no error in my code, your formulas are compatible as far as written... – Lutz Lehmann Aug 17 '17 at 10:56
  • Thanks for answering. What I did was to rationalize all numbers and worked with illimited precision. I shall repeat all of that tomorrow. I think that we can establish easily a better guess of the solution and converge faster. If I find anything new, I shall let you know. Cheers. – Claude Leibovici Aug 17 '17 at 13:16
  • I found a typo in my code. Sorry for having disturbed ! Cheers. – Claude Leibovici Aug 18 '17 at 03:00
0

Instead of solving$$\frac{Q}{k\left(\frac{\frac{h^2}{p}+bh}{b+2h\sqrt{1+\frac{h^2}{p^2}}}\right)^\frac{2}{3}\sqrt{J}\left(b+\frac{h}{p}\right)h} = h$$ I (personally) would prefer to solve $$\frac{Q}{k \sqrt J}={\left(\frac{\frac{h^2}{p}+bh}{b+2h\sqrt{1+\frac{h^2}{p^2}}}\right)^\frac{2}{3}\left(b+\frac{h}{p}\right)h^2}$$ which is better conditioned.

The interesting point is that, if $h$ is small, we can expand as a Taylor series and get as a first estimate $$h_0=\left(\frac{Q}{b k\sqrt{J} }\right)^{3/8}$$ (by Darboux theorem, this is an overestimate of the solution) from which Newton method would converge quite fast as shown below. $$\left( \begin{array}{cc} n & h_n \\ 0 & 0.15698235371520257277 \\ 1 & 0.12595872270022229897 \\ 2 & 0.11498756631240531199 \\ 3 & 0.11367221987381462407 \\ 4 & 0.11365448999349025184 \\ 5 & 0.11365448680525111214 \\ 6 & 0.11365448680525100906 \end{array} \right)$$

What also could be of interest is to use higher order methods (say of order $k$) which would generate as a second estimate the values given below $$\left( \begin{array}{cc} k & h_1^{(k)} & \text{method} \\ 2 & 0.12595872270022229897 & \text{Newton}\\ 3 & 0.11875238571244777181 & \text{Halley}\\ 4 & 0.11606655679401249589 & \text{Householder}\\ 5 & 0.11487870810033094636 & \text{no name} \end{array} \right)$$