Этап. Поиск начального приближения

Пусть x₁ = 1; F(1) = 0,1 – ln 1 = 0,1 >0; (a)

x₂ = 2; F(2) = 0,4 – 2* ln 2 < 0; (b)

Поскольку функция имеет разные знаки на границах участка [a,b], она проходит через нуль на этом участке и в качестве начального приближения можно взять значение a или b. Удобнее принять a = 1, т.е. x₀ = 1.

2 этап. Цикл приближённого вычисления корня

Начальное приближение x₀ =1. Будем искать уточнённое значение x, при котором

F(x) = 0, т.е. 0,1x² –x*ln x = 0.

Для поиска решения выбираем метод, при котором последовательно, шаг за шагом, производится подстановка значений x в уравнение, а полученное на каждом шаге значение F(x) анализируется и уточняется. Вычисления производятся до тех пор, пока значение функции F(x) не приблизится к 0 с заданной точностью. Последнее значение x и будет искомым корнем уравнения. Такой метод широко используется в вычислительной математике и носит название метода итераций (последовательных приближений).

Итерацией называется один шаг вычислений, причём алгоритм каждой итерации один и тот же. Это даёт возможность организовать вычисления в виде цикла, прерываемого при достижении заданной точности вычисления функции. При числе итераций n, стремящемся к бесконечности, значение x_n стремится к истинному значению корня c, при котором F(c) = 0. Если у последовательности x_n есть предел c, и этот предел является корнем F(c) = 0, то итерационный процесс называется сходящимся. В противном случае решение не может быть получено данным методом.

При сходящемся итерационном процессе для любого заданного положительного значения точности eps > 0 существует неравенство

| x_n+1 – x_n | < eps.

Для вычисления корня с заданной точностью eps необходимо построить цикл вычислений так, чтобы это неравенство проверялось на каждом шаге (итерации). При выполнении неравенства цикл прекращается, и полученное значение x_n+1 принимается равным искомому корню уравнения x_n+1 = c при заданной точности eps.

Для реализации изложенных выше принципов численного решения уравнений используется два основных метода: метод половинного деления и метод касательных (Ньютона). Каждый из них имеет свои преимущества и недостатки, и выбор метода определяется видом уравнения, характеристиками вычислительной техники и другими обстоятельствами. Рассмотрим вначале

Метод половинного деления

Задано уравнение F(x) =0, причём функция F(x) – непрерывная. В качестве начального приближения используется отрезок аргумента x в диапазоне [a,b] (рис.18 ). Отрезок должен быть выбран, как указывалось ранее, таким образом, чтобы значения функции при подстановке в неё границ отрезка a,b имели разный знак:

F(a)*F(b) <0.

Это значит, что в выбранном диапазоне аргумента x функция меняет знак, т.е. проходит через 0, что и соответствует искомому значению корня. Далее формируется итерационный процесс в следующем порядке:

Первая итерация

Отрезок [a,b] делится пополам и вычисляется значение функции в середине участка в точке (a+b)/2

F((a+b)/2)=

При этом полученное значение функции может оказаться либо равным, либо не равным нулю. В первом случае, при F=0, середина отрезка x = (a+b)/2, и будет являться искомым корнем, обращающим функцию в нуль. Если значение функции в середине участка отлично от нуля, то надо определить знак этого значения и сравнить его со знаками функции в точке a и в точке b.

Теперь надо выбрать ту из половин отрезка [a,b], на концах которой функция приобретает значения с разными знаками, как обуславливалось при выборе первоначального отрезка [a,b]. Пусть

F(a) > 0, F(b) < 0, F((a+b)/2) >0.

Тогда в качестве новых границ участка следует выбрать b и (a+b)/2, т.к. произведение функций от этих значений меньше нуля, что свидетельствует о наличии корня уравнения на выбранном участке. Обозначим границы нового отрезка, составляющего половину исходного, значениями [a₁, b₁].

Рис.18. Рис.19

Вторая итерация

Отрезок [a₁,b₁] делится пополам и вычисляется значение функции в середине участка в точке (a₁ + b₁)/2:

F((a₁+b₁)/2).

Теперь производится повторение анализа, выполненного при первой итерации. Если F((a₁+b₁)/2) = 0, то середина участка (a₁+b₁)/2 и является искомым значением корня, обращающим функцию в ноль. В противном случае вновь определяются знаки, которые принимает функция при подстановке в неё значений концов участка a₁ и b₁. Пусть

F(a₁)>0, F(b₁)<0, F((a₁+b₁)/2 >0.

Тогда в качестве нового участка берётся та половина отрезка, у которой значения функции на её концах имеют разные знаки, т.е. половина отрезка с координатами b₁ и (a₁+b₁)/2. Обозначим эти значения как [a₂, b₂].

Третья итерация и, в случае необходимости, последующие итерации производятся аналогичным образом с использованием циклического алгоритма вычислений. В результате выполнения цикла вычислений на некоторой итерации длина очередного отрезка, полученного путём половинного деления, станет меньше заданной точности вычислений eps, т.е. начнет выполняться неравенство

|a_n – b_n| < eps

После этого цикл вычислений прекращается, и величины a или b принимаются за искомое значение корня c, обращающее функцию в нуль.

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

Другим распространённым методом численного решения уравнений является

Метод касательных (Ньютона)

Метод касательных, как и метод половинного деления, основан на циклическом итерационном алгоритме. Однако здесь для каждой итерации используется выражение, связанное с первой производной функции, входящей в уравнение. Поэтому метод применим только для непрерывных и дифференцируемых функций.

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

F(a)*F(b) < 0.

Выполнение этого условия свидетельствует о том, что функция F(x) в интервале [a,b] имеет нулевое значение, т.е. корень x₀. Примем за начальное приближение корня x₀ одну изграниц выбранного участка x₀ = a или x₀=b.

Вычислим производную F’(x) заданной функции F(x) в точке начальногоприближенияи запишем итерационную формулу нахождения корня уравнения

x_n+1 = x_n – F(x_n)/F’(x_n)

Тогда значение корня после первой итерации

x₁ = x₀ – F(x₀)/F’(x₀)

а после второй итерации

x₂ = x₁ – F(x₁)/F’(x₁)

и т.д.

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

Условием окончания итерационного процесса является достижение заданной точности eps вычисления корня уравнения, т.е. выполнение условия

| x_n+1 – x_n | < eps

В качестве искомого корня уравнения принимается значение x_n+1, полученное на последней итерации.

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

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

неопределённость из-за недопустимости деления на нуль. В этом случае следует изменить начальное приближение на малое число, чтобы значение производной отличалось от нуля.

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

ЛЕКЦИЯ 9