Приближённые методы решения алгебраического уравнения (стр. 4 из 4)

Покажем, что последовательность {x_n} стремится к корню уравнения (1.0) монотонно.

Предположим для определённости, что f ¢(x) и f ¢¢(x) >0, a<x<b (рис 1.8). В этом случае функция f(x) строго монотонна и строго выпукла вниз. Следовательно, любая внутренняя точка хорды, соединяющей крайние точки графика функции f(x), лежит над соответствующей точкой графика функции f(x), т. е.

l(x) > f(x), a > x > b

В частности, если х₀ корень уравнения (1.1): f(x₀) = 0, отсюда следует, что

l(x₀) > 0

C (3.8) и (4.8) получаем:

l(x) = 0, a > x₁ > b

Таким образом,

l(x₁) < l(x₀) (5.8)

но линейная функция l(x) строго монотонно возрастает, так как

l(b) = f(b) > f(a) = l(a)

поэтому из (5.8) следует x₁ < x₀ , заменяя теперь отрезок [a, b] отрезком [x₁, b] и замечая, что f(x₁) < 0 , аналогично можно доказать, что x₁ < x₂ < x₀, далее по индукции получим:

x₁ < x₂ < … < x_n < … < x₀,

Таким образом, последовательность {x_n}, будучи монотонной, сходится. Пусть lim x_n = c, при n®¥ . Переходя к пределу при n®¥ в равенстве (4.8) получим f(c)=0, т. е. последовательность {x_n} сходится к корню уравнения (1.1).

Если | f ¢(x)|³m>0, a<x<b, то не трудно получить оценку погрешности сходимости последовательности {x_n} через значения самой функции f(x) в точках x_n. Действительно,

f(x_n)= f(x_n)- f(x₀)= f ¢(x_n)×(x_n-x₀),

x_n<x_n<x₀, n = 1, 2, …,

Отсюда:

, n = 1, 2, …,

Остальные случаи, т. е. случаи:

,

,

рассматриваются аналогично разобранному (рис 2.8).

рис. 2.8

9. Усовершенствованный метод хорд

Если итерационная последовательность, полученная методом хорд, сходится, то скорость сходимости будет такой же, как и у метода итераций, - погрешность значения корня убывает, как геометрическая прогрессия. Существует усовершенствование способа хорд, дающее гораздо более быструю сходимость. В обычном методе хорд мы на каждом шагу используем один из концов отрезка [a, b] последнее получившееся приближение. Вместо этого можно использовать два последних приближения – ведь они ближе к искомому корню, чем концы отрезка [a, b].

рис.1.9 а) б)

Формула, при которой мы используем два последних приближения, имеет вид:

(1.9)

При этом а₁ вычисляется по формуле:

а а₂ в зависимости от знаков f(a), f(b), f(a₁), если f(a)<0, f(b)>0,

, f(a₁)<0

, f(a₁)>0

Если случайно окажется, что точка а₃, вычисленная по формуле (1.9), лежит за пределами отрезка [a, b], то на следующем шаге надо вместо этой точки взять ближайший к ней конец этого отрезка (рис. 1.9, б). Оказывается, что сходимость усовершенствованного метода хорд гораздо быстрее, чем у обычного. Именно, если x - корень уравнения f(x)=0, то:

|a_{n+ 1}|<C×|a_n-x| ^S, где

10. Комбинированный метод решения уравнений

При решении уравнений часто комбинируют методы хорд и Ньютона. Если график функции y=f(x) обращён вогнутостью вверх, то находят точки а₁ и х₁ по формулам:

(1.10)

(2.10)

Если же график функции y=f(x) обращён вогнутостью вниз, то точку а₁ находят по формуле (1.10), а точку х₁ – по формуле:

(3.10)

Как видно из рис.1.10 а) и б), корень x уравнения f(x)=0 лежит обычно между полученными точками а₁ и х₁. Применяя снова к этим точкам формулы метода хорд и метода Ньютона, получают новую пару точек а₂ и х₂ и т. д.

Таким путём получают две последовательности точек а₁, а₂, а₃, …, a_n, … и x₁, x₂, x₃, … , x_n, …, приближаются с разных сторон к искомому корню x. Преимущество описанного метода состоит в том, что при нём получаются приближённые значения как с избытком так и с достатком.

рис.1.10

а) б)

11. Заключительные замечания

Ситуация, когда одну и ту же задачу можно решить многими способами, является довольно типичной. В таких случаях естественно возникает необходимость сравнения их между собой.

При оценке эффективности численных методов существенное значение имеют различные свойства:

универсальность;

простота организации вычислительного процесса и контроля над точностью;

скорость сходимости.

Наиболее универсальным является метод деления пополам (дихотомии): он только требует непрерывности функции. Остальные методы накладывают более сильные ограничения. Во многих случаях это преимущество метода вилки может оказаться существенным.

С точки зрения организации вычислительного процесса все виды численного нахождения корней уравнения очень просты. Однако и здесь метод деления пополам обладает некоторым преимуществом. Вычисления можно начинать с любого отрезка [a, b], на концах которого непрерывная функция f(x) принимает значения разных знаков. Процесс будет сходится к корню уравнения f(x)=0, причём на каждом шаге он даёт для корня двустороннюю оценку, по которой легко определить достигнутую точность. Сходимость же метода итераций или касательных зависит от того, насколько удачно выбрано нулевое приближение.

Наибольшей скоростью сходимости обладает метод касательных. В случае, когда подсчёт значений функции f(x) сложен и требует больших затрат машинного времени, это преимущество становится определяющим. На вопрос о том, какой метод – метод итераций или дихотомия даёт большую скорость сходимости, однозначно ответить нельзя. При методе дихотомии знаменатель геометрической прогрессии убывания погрешности равен q=0.5, а при методе хорд он может принимать значения 0<q<1.

Из вышесказанного следует, что ответ на вопрос о наилучшем численном методе решения уравнения не однозначен. Он существенно зависит от того, какую дополнительную информацию о данной функции мы имеем, в соответствие с этим, каким свойствам метода придаём большее значение.

При обосновании метода итераций и метода Ньютона на функции j(x) и f(x), а также на выбор начального приближения х₀ накладывались определённые ограничения. Однако при решении конкретных задач проверить их выполнение часто бывает трудно и даже практически не возможно. Функция может не задаваться в виде простой формулы, а находится в результате численного решения некоторой математической задачи, получаться из измерений и проверять «экспериментально»: начинают расчёт и следят за поведением первых членов последовательности {x_n}. Если по ним видно, что процесс сходится, то расчёт продолжают, пока не достигнут нужной точности. В противном случае вычисления прекращают и анализируют полученные данные, пытаясь установить причину рассходимости и, в соответствии с ней выбрать другой метод решения задач.

Список литературы

А. Н. Тихонов, Д. П. Костомаров «Вводные лекции по прикладной математике»

М. «Наука» 1984

Л. Д. Кудрявцев «Математический анализ т. 2» М. 1984 «Наука»

П. Ф. Фильчаков «Справочник по высшей математике» К. 1973 «Наукова Думка»

Н. Н. Калиткин «Численные методы» М. «Наука» 1978

Н. Я. Виленкин «Итерационные методы» М. «Наука» 1984