% 
% Steffenson 迭代
%

clear all; 
close all;

f = @(x) x^3 - x - 1;
g = @(x) x^3 - 1;

xt = fzero(f, [1,2]); % 精确解
fprintf('True solution: xt = %.8f\n\n', xt)

itermax = 10;  % 设置最大迭代步数
x = 1.5;       % 迭代初始值
tol = 1e-6;    % 精度要求（函数值）

% 不动点迭代
fprintf('普通不动点迭代\n')
for k = 1 : itermax
    x   = g(x);
    fx  = f(x); 
    fprintf('k = %d, x = %.8f, fx = %.2e\n', k, x, fx);
    if (abs(fx) < tol), break, end
end
   
% Steffenson 迭代
x    = 1.5;          % 迭代初始值
err0 = abs(x - xt);  % 初始误差
fprintf('===================\n\n');
fprintf('Steffenson 迭代\n');
for k = 1 : itermax
    x1 = g(x); 
    x2 = g(x1);
    x_new  = x - (x1 - x)^2 / (x2 - 2*x1 + x);
    fx = f(x_new);
    err = abs(x_new - xt);
    x = x_new;
    fprintf('k = %d, x = %.8f, fx = %.2e, err = %.2e, order = %.2f\n', ...
        k, x, fx, err, log(err)/log(err0));
    if (abs(fx) < tol), break, end
end