Метод хорд (метод линейной интерполяции) нахождение корней уравнения


 

Метод простых итераций во всех рассмотреннных вариантах использует для построения очередного приближения $ x_{i+1}$ только информацию о функции в одной лишь точке $ x_i$; при этом никак не используются предыдущие значения $ x_{i-1}, x_{i-2},\dots\;.$ Однако эту предыдущую информацию также можно использовать при нахождении $ x_{i+1}$. В качестве примера такого метода мы приведём метод, основанный на нахождении $ x_{i+1}$ по двум предыдущим приближениям $ x_i$ и $ x_{i-1}$ с помощью линейной интерполяции, называемый методом хорд.

Идея метода состоит в том, что по двум точкам $ M_{i-1}(x_{i-1};f(x_{i-1}))$ и $ M_i(x_i;f(x_i))$ построить прямую $ M_{i-1}M_i$ (то есть хорду, соединяющую две точки графика $ y=f(x)$) и взять в качестве следующего приближения $ x_{i+1}$ абсциссу точки пересечения этой прямой с осью $ Ox$. Иными словами, приближённо заменить на этом шаге функцию $ f(x)$ её линейной интерполяцией, найденной по двум значениям $ x$: $ x_{i-1}$ и $ x_i$. (Линейной интерполяцией функции $ f(x)$ назовём такую линейную функцию $ \ell(x)$, значения которой совпадают со значениями $ f(x)$ в двух фиксированных точках, в данном случае -- в точках $ x_{i-1}$ и $ x_i$.) Вычислить тройной интеграл

В зависимости от того, лежат ли точки $ x_{i-1}$ и $ x_i$ по разные стороны от корня $ x^*$ или же по одну и ту же сторону, получаем такие чертежи:

Рис.9.14.Построение последовательного приближения по методу хорд: два случая
[an error occurred while processing this directive]

Итак, очередное последовательное приближение будет зависеть от двух предыдущих: $ x_{i+1}={\varphi}(x_{i-1};x_i)$. Найдём выражение для функции $ {\varphi}$.

Интерполяционную линейную функцию $ \ell(x)$ будем искать как функцию с угловым коэффициентом, равным разностному отношению

$\displaystyle k_i=\dfrac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}},$

построенному для отрезка между $ x_{i-1}$ и $ x_i$, график которой проходит через точку $ M_i$:

$\displaystyle \ell(x)=f(x_i)+\dfrac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}}(x-x_i).$

Решая уравнение $ \ell(x)=0$, находим

$\displaystyle x_{i+1}=\dfrac{x_{i-1}f(x_i)-x_if(x_{i-1})}{f(x_i)-f(x_{i-1})}=
x_i-\dfrac{f(x_i)}{\dfrac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}}},$

то есть

$\displaystyle x_{i+1}=x_i-\dfrac{f(x_i)}{k_i}.$(9.3)
 


Заметим, что величина $ k_i$ может рассматриваться как разностное приближение для производной $ f'(x)$ в точке $ x_i$. Тем самым полученная формула (9.3) -- это разностный аналог итерационной формулы метода Ньютона.

Вычисление по формуле (9.3) гораздо предпочтительнее вычисления по другой полученной нами формуле

$\displaystyle x_{i+1}=\dfrac{x_{i-1}f(x_i)-x_if(x_{i-1})}{f(x_i)-f(x_{i-1})},$

хотя эти две формулы математически тождественны, поскольку при использовании формулы (9.3) в случае вычислений с округлениями (например, на компьютере) достигается меньшая потеря значащих цифр.

Имеются две разновидности применения формулы (9.3).

Первая разновидность: вычисления ведутся непосредственно по формуле (9.3) при $ i=1,2,3,\dots$, начиная с двух приближений $ x_0$ и $ x_1$, взятых, по возможности, поближе к корню $ x^*$. При этом не предполагается, что $ x^*$ лежит между $ x_0$ и $ x_1$ (и что значения функции $ f$ в точках $ x_0$ и $ x_1$ имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между $ x_{i-1}$ и $ x_i$ на каком-либо следующем шаге (хотя это и не исключено). В таком случае затруднительно дать оценку погрешности, с которой $ x_{i+1}$ приближает истинное значение корня $ x^*$, и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство $ \vert x_{i+1}-x_i\vert<{\varepsilon}$, где $ {\varepsilon}$ -- желаемая точность нахождения корня. При этом полагают приближённое значение корня равным $ \wt x=x_{i+1}$.