Problem with convergence using newtons method

61 vues (au cours des 30 derniers jours)
Adil
Adil le 22 Mar 2023
Modifié(e) : John D'Errico le 22 Mar 2023
I'm trying to solve a non-linear equation using newtons method and I'm really struggling with trying to prove that newtons method has a quadratic convergence. I have found the t value that solves the equation however I have failed in proving that it converges. The assignment states that we have to find the absolute value of one error and then dividing it by the error in the previous iteration squared as shown:
Now M is meant to be a constant as it converges, however my graph looks something like this:
I have tried setting a new guessing value t and checking the function and derivative with no success. Any help would be greatly appreciated
t = 10;
guess = [];
error = [];
tol = 1e-9;
iter = 100;
diff = 1;
f = @(t) ps(t) * 1.2 - pf(t);
fp = @(t) (-ps(t)*1.2*ks*exp(-ks*t) - kf*pf(t)*((pfmax/p0)-1)*exp(-kf*t));
for i = 1:iter
tnext = t - (f(t)/fp(t));
diff = abs(tnext-t);
t = tnext;
guess(i) = t;
error = [fel, diff];
if diff < tol
break
end
end
kon = error(2:end)./error(1:end-1).^2;
n = length(kon);
iiter = 1:n;
loglog(iiter, kon, "-o");
xlabel("iteration")
ylabel("y")

Réponses (1)

John D'Errico
John D'Errico le 22 Mar 2023
Modifié(e) : John D'Errico le 22 Mar 2023
First, you CANNOT prove that Newton's method has quadratic convergence using any existing function, or any such piece of code.
At best, you can SHOW that it does appear to be quadratically convergent, on one example.What would that mean? Look at the sequence of iterates. For example...
f = @(x) x.^3 - 3*x.^2 + 2*x - 1;
First, note the true solution to the problem is:
syms X
fsol = vpa(solve(f(X),'maxdegree',3))
fsol = 
x_true = double(fsol(1))
x_true = 2.3247
fplot(f,[-2,4])
yline(0)
So there appears to be one real root that lies between [2,3] on the real line. A Newton iteration is basic. I will do the iterations in a symbolic form though, because otherwise, you won't really see the quadratic convergence happening.
df = @(x) 3*x.^2 - 6*x + 2;
xiter = NaN(100,1);
x0 = 3;
xiter(1) = x0; % initial point
xtol = 1e-15;
iter = 1;
maxiter = 100;
xstep = inf;
while (iter < maxiter) && (abs(xstep) > xtol)
iter = iter + 1;
fx = f(x0);
dfx = df(x0);
xstep = -fx/dfx;
x0 = x0 + xstep;
xiter(iter) = x0;
end
xiter(iter+1:end) = [];
format long g
xiter
xiter = 8×1
3 2.54545454545455 2.35961491591518 2.32580134500585 2.32471904941713 2.32471795724586 2.32471795724475 2.32471795724475
Is this quadratically convergent?
dx = xiter - x_true
dx = 8×1
0.675282042755254 0.2207365882098 0.0348969586704384 0.00108338776109917 1.09217237964643e-06 1.11199938146456e-12 4.44089209850063e-16 4.44089209850063e-16
A hallmark of quadratic convergence is you will see a doubling of the number of correct digits at each iteration, until double precision craps out on you at least. We see exactly that here, as the error decreases at each step. Do you see the error going down from approximately 0.03 to 1e-3, to 1e-6, to 1e-12? Each time the error is the square of the previous error, and since these errors are less than zero, they get small very rapidly.
But that is not a proof of quadratic convergence. It merely exhibits what appear to be quadratic convergence, on this specific problem.
Had I done the above computations using vpa and symbolic tools, we could track those errors going to zero very nicely for many, many iterations.

Produits


Version

R2022b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by