Feb 9, 2016
Tianshu Yuan
Q1:
MATLAB algorithm code:
x = 2.0;
nmax = 25;
eps = 1;
xvals = x;
n = 0;
relative_error = [];
correct_digits = [];
while eps >= 1e-7&&n <= nmax;
y = x - (1/x + log(x) - 2) / (-1/(x^2) +1/x);
xvals = [xvals;y];
eps = abs(y-x);
x = y;
n = n + 1;
end
for i = 1:n+1;
relative_error = [relative_error; abs((xvals(i) - xvals(n+1))/(xvals(n+1)))];
end
for i = 1:n+1;
correct_digits = [correct_digits; floor(-log2(relative_error(i)))];
end
index = []
for i = 1:n+1;
index = [index;i]
end
T=table(index ,correct_digits);
disp(T);
First, when we set x0 = 0.2 as the first approximation, by 6 iterations, we find the solution for f(x) , 0.317844432899373.
The tables of xvals and correct digits,
index correct_digits
_____ ______________
1 1
2 2
3 5
4 10
5 19
6 39
7 Inf
Second, we set x0 = 2.0 as the first approximation, by 5 iterations, we find the solution for f(x), 6.305395279271693
The tables of xvals and correct digits
index correct_digits
_____ ______________
1 0
2 2
3 6
4 13
5 29
6 Inf
It’s easy to see from the table that the convergence of Newton’s Method is quadratic.
Q2
We use the same algorithm as Q1. And we find that,
index correct_digits
_____ ______________
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 4
9 4
10 5
11 5
12 6
13 7
14 7
15 8
16 8
17 9
18 9
19 10
20 11
21 11
22 12
23 12
24 13
25 14
26 14
27 15
It is clear that it become converging linearly. This is mainly because when x -> roots, f(x) ->0, f’(x)->0. And actually we can rewrite the algorithm as: \(x_{n+1} = x_{n} - \frac{x_{n}^3}{3x_{n}^2} = \frac{2}{3}x_{n}\)
This could seen as a fixed-point iteration, where \(g(x) = \frac{2}{3}x\).
| Therefore, $$ | x_{n} - x | = | g(x_{n-1}) - g(x) | = \frac{2}{3} | x_{n-1}-x | $$ |
Rate of convergence, \(O((\frac{2}{3})^n)\)
Q3
Code:
convergence = [];
for i = 0.1:0.1:3;
xvals = hw3_q3(i); %hw3_q3 is a function using the same algorithm in Q2
if abs(xvals(length(xvals)) - 0) <= 1e-8
convergence = [convergence; i];
end
end
Using matlab to find the convergence intervals for (0.1,0.2,…20), the result is as follows:
convergence =
0.100000000000000
0.200000000000000
0.300000000000000
0.400000000000000
0.500000000000000
0.600000000000000
0.700000000000000
0.800000000000000
0.900000000000000
1.000000000000000
1.100000000000000
1.200000000000000
1.300000000000000
Clearly when x >=1.4 or so, the algorithm is going to diverse.
Using the same algorithm above, set x0 = -1 it took 5 iterations to get the solutions.
xvals =
-1.000000000000000
0.570796326794897
-0.116859903998913
0.001061022117045
-0.000000000796310
0
When x0 is set as -2, the iteration becomes divergent.
xvals =
1.0e+168 *
-0.000000000000000
0.000000000000000
-0.000000000000000
0.000000000000000
-0.000000000000000
0.000000000000000
-0.000000000000000
0.000000000000000
-0.000000000000000
6.999943395317582
-Inf
NaN
To achieve oscillation, the roots of \(arctanx - \frac{2x}{1+x^2} = 0\) should be set as the initial approximation.
Using matlab to find the roots of the equation above,
\[x_{1} = -1.391745200270735, x_2 = 1.391745200270735\]If set the two roots as the initial approximation for the Newton’s Method, the oscillation would occur, like following:
xvals =
-1.391745200270735
1.391745200270735
-1.391745200270735
1.391745200270735
-1.391745200270735
1.391745200270735
-1.391745200270735
1.391745200270735
-1.391745200270735
...
Conclusion: x0 = -1, lead to convergence ; x0 = -2, lead to divergence; x0 = 1.391745200270735 or -1.391745200270735 lead to oscillation.
Q4
(a)
\[f(x) = x^2 - 2bx + b^2 -d^2, b>0 ,d>0\] \[x_{k+1} = x_{k} - \frac{x_k^2-2bx_k+b^2-d^2}{2(x_k-b)} = \frac{x_k^2-b^2+d^2}{2(x_k-b)}\] \[x_{k+1} = g(x_k)\]where \(g(x_k) = \frac{x_k^2-b^2+d^2}{2(x_k-b)}\)
(b)
\[g'(x) = \frac{x^2 - b^2 +d^2}{2(x-b)} = \frac{1}{2} - \frac{d^2}{2(x-b)^2}\]| Therefore, $$ | g’(x) | = | \frac{1}{2} - \frac{d^2}{2(x-b)^2}$$ |
| Because $$ | x -b | \geq \frac{d}{\sqrt2}\(, we can get\) 0 \leq \frac{d^2}{2(x-b)^2} \leq 1$$ |
| Therefore, $$ | g’(x) | = | \frac{1}{2} - \frac{d^2}{2(x-b)^2} | \leq \frac{1}{2}$$ |
(c)
\[|g(x) - b| = | \frac{x-b}{2} + \frac{d^2}{2(x-b)^2}|\]| Since we know that $$ | a+b | \geq 2\sqrt{ab}$$ |
(d)
We have already prove that x = g(x) will converge through (b) and (c)
It is clear that the interval that guarantee convergence is \((-\infty,b)U(b,+\infty)\)
Only when you choose \(x_0\) as b, \(f'(x) = 0\) Otherwise, from any point on the graph, it should be able to converge.
Q5
According to the equation \(f(x_k) +f'(x_k)(x-x_k) + \frac{1}{2} f''(x)(x-x_k)^2 = 0\)
So considering fixed point iteration, let \(x = g(x)\) so that f(x) = g(x) - x
Derive the \(f(x) + f'(x) (g(x) - x) + \frac{1}{2}f''(x) (g(x) - x)^2 = 0\) equation implicitly.
We get \(2g'(x) = \frac{-(g(x) - x)^2f'''(x)}{f'(x)+(g(x)-x)f''(x)} = -\frac{f^2(x)f'''(x)}{f'(x)+f(x)f''(x)}\),
let r be the root of f(x), so that f(r) = 0 and r = g(r). It’s obvious that \(g'(r) = 0\)
\(g'(x)\) can be also expressed in this way, \(g'(x) = f^2(x) * q(x)\)
So that \(g''(x) = 2f(x)f'(x)q(x) + q'(x)f^2(x)\) Therefore, \(g''(r) = 0\)
Assuming that \(f'(x) \neq 0\) and \(f(x)f''(x) > 0\), therefore \(g'''(r) \neq 0\)
\[|2g'(x)| = |\frac{f^2(x)f'''(x)}{f'(x)+f(x)f''(x)}| \leq |\frac{f^2(x)f'''(x)}{f'(x)}|\]Taylor expansion of f(x) about r should be: \(f(x) = f(r) + f'(r)(x-r) + O(|x-r|^2) = f'(r)(x-r) + O(|x-r|^2\)
| if $$ | x-r | \leq \delta_0 $$ |
| then $$ | f(x) | \leq \varepsilon $$, which should lead to derivative of g(x) less than 1 |
And let \(\delta \leq \frac{1}{max(f'(x)f'''(x))}\)
| Therefore $$ | 2g’(x) | = O(f’(x) | x-r | ^2f’’‘(x)) < 1$$ |
| And $$ | x-r | < \sqrt{\delta}$$ would guarantee the convergence since there exist a |
\(\delta_1\) such that on the interval g(x) maps the interval to itself because of the assumptions.
\[g(x) = g(r) + g'(r)(x-r) + \frac{1}{2}g''(r)(x-r)^2 + \frac{1}{3!}g'''(r)(x-r)^3\] \[x_{n+1} = g(x_n) = g(x_n) + \frac{1}{3!}g'''(r)(x_n-r)^3\]\(x_{n+1} - r = \frac{1}{3!}g'''(r)(x_n-r)^3\) which give us cubic convergence.
comments powered by Disqus