Решение нелинейных уравнений

Пусть требуется решить уравнение

Где
– нелинейная непрерывная функция.

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

Полное решение поставленной задачи можно разделить на 3 этапа:

Установить количество, характер и расположение корней уравнения (1).

Найти приближенные значения корней, т.е. указать промежутки, в которых наудится корни (отделить корни).

Найти значение корней с требуемой точностью (уточнить корни).

Существуют различные графические и аналитические методы решения первых двух задач.

Наиболее наглядный метод отделения корней уравнения (1) состоит в определении координат точек пересечения графика функции
с осью абсцисс. Абсциссы точек пересечения графика
с осью
являются корнями уравнения (1)

Промежутки изоляции корней уравнения (1) можно получить аналитически, опираясь на теоремы о свойствах функций, непрерывных на отрезке.

Если, например, функция
непрерывна на отрезке
и
, то согласно теореме Больцано – Коши, на отрезке
существует хотя бы один корень уравнения (1)(нечетное количество корней).

Если функция
удовлетворяет условиям теоремы Больцано-Коши и монотонна на этом отрезке, то на
существует только один корень уравнения (1).Таким образом, уравнение (1) имеет на
единственный корень, если выполняются условия:

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

Полезным средством для отделения корней является также использование теоремы Штурма.

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

Пример Решим уравнение
методом простой итерации . Зададим
. Построим график функции.

На графике видно, что корень нашего уравнения принадлежит отрезку
, т.е.
– отрезок изоляции корня нашего уравнения. Проверим это аналитически, т.е. выполнение условий (2):

Напомним, что исходное уравнение (1) в методе простой итерации преобразуется к виду
и итерации осуществляются по формуле:

(3)

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

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

На практике часто выражают
непосредственно из уравнения (1). Если не выполняется условие сходимости, преобразуют его к виду (3) и подбирают. Представим наше уравнение в виде
(выразим x из уравнения). Проверим условие сходимости метода:

для
. Обратите внимание, что условие сходимости выполняется не
, поэтому мы и берем отрезок изоляции корня
. Попутно заметим, что при представлении нашего уравнения в виде
, не выполняется условие сходимости метода:
на отрезке
. На графике видно, что
возрастает быстрее, чем функция
­­ (|tg| угла наклона касательной к
на отрезке
)

Выберем
. Организуем итерации по формуле:

Программно организуем процесс итераций с заданной точностью:

> fv:=proc(f1,x0,eps)

> k:=0:

x:=x1+1:

while abs(x1-x)> eps do

x1:=f1(x):

print(evalf(x1,8)):

print(abs(x1-x)):

:printf("Кол. итер.=%d ",k):

end :

На 19 итерации мы получили корень нашего уравнения

c абсолютной погрешностью

Решим наше уравнение методом Ньютона . Итерации в методе Ньютона осуществляются по формуле:

Метод Ньютона можно рассматривать как метод простой итерации с функцией, тогда условие сходимости метода Ньютона запишется в виде:

.

В нашем обозначении
и условие сходимости выполняется на отрезке
, что видно на графике:

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

Программно организуем процесс итераций с заданной точностью. На 4 итерации получим корень уравнения

с
Мы рассмотрели методы решения нелинейных уравнений на примере кубических уравнений, естественно, этими методами решаются различные виды нелинейных уравнений. Например, решая уравнение

методом Ньютона с
, находим корень уравнения на [-1,5;-1]:

Задание : Решить нелинейные уравнения с точностью

0.

деления отрезка пополам (дихотомии)

простой итерации.

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

секущих – хорд.

Варианты заданий рассчитываются следующим образом: номер по списку делится на 5 (
), целая часть соответствует номеру уравнения, остаток – номеру метода.

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

Приведенное описание функции пригодно для всех версий системы МС. Эту функцию можно вызвать с помощью кнопки f(x) на панели инструментов, выбрав в левом списке пункт Solving. В МС14 выбранная таким образом функция имеет четыре аргумента. Первые два из них − такие же, как было описано выше, а третьим и четвертым аргументами служат левая и правая границы интервала, на котором лежит искомый корень. Если задать третий и четвертый аргументы, то начальное значение переменной можно и не присваивать.

Рассмотрим использование этой функции на примере уравнения
. Сначала выполним отделение корней. Для этого построим графики функций в правой и левой части (рис.19). Из рисунка видно, что уравнение имеет два корня. Один лежит на отрезке [–2; 0], другой же – на . Воспользуемся первым вариантом формата функцииroot. Правый корень уравнения по графику приближенно равен 1. Поэтому выполним присвоение x := 1, вызовем функцию root, укажем два первых аргумента
и нажмем клавишу =. На экране получим результат 1.062. Теперь воспользуемся вторым вариантом шаблона. Снова вызовем функциюroot, укажем четыре аргумента и нажмем клавишу =. На экране получим результат

Второй корень найдем так:

Число выведенных на экран знаков вычисленного корня не совпадает с точностью нахождения результата. В памяти компьютера число хранится с пятнадцатью знаками, а на экран из этой записи выводится то количество знаков, которое установлено в меню Format. Насколько найденное значение корня отличается от точного, зависит от метода вычисления корня и от числа итераций в этом методе. Это регулируется системной переменной TOL, которая по умолчанию равна 0,001. В системе МС14 функция root ориентирована на достижение точности
, если
, и на достижение точности, задаваемое переменнойTOL, если ее значение меньше
. Значение этой переменной меньше, чем
, задавать не рекомендуется, т.к. может нарушиться сходимость вычислительного процесса.

Следует учесть, что в некоторых исключительных случаях результат может отклоняться от точного значения корня значительно больше, чем на величину TOL. Изменить значение TOL можно или простым присвоением, или с помощью меню Tools пункт Worksheet Options пункт Built-In Variables.

Для нахождения корней многочлена можно воспользоваться другой функцией, которая выдаст все корни многочлена, включая комплексные. Это функция polyroots(■), где аргументом служит вектор, координатами которого являются коэффициенты многочлена, первая координата – свободный член, вторая – коэффициент при первой степени переменного, последняя – коэффициент при старшей степени. Функция вызывается так же, как и функция root. Например, корни многочлена
можно получить так:

.

Некоторые простые уравнения можно решать и с помощью символьных преобразований. Можно найти корни многочлена второй или третьей степени, если коэффициенты являются целыми числами или обыкновенными дробями. В качестве примера возьмем многочлены, корни которых известны. Эти многочлены мы получим как произведение линейных множителей. Возьмем многочлен
. Получим его запись по степенямx . Для этого, как было описано в первом занятии, выделим в этой записи переменное x , выберем в меню Symbolics пункт Variable и в раскрывшемся окне пункт Collect:

.

В полученном результате выделим переменное x , выберем в меню Symbolics пункт Variable и в раскрывшемся окне пункт Solve. Получим

.

Как видим, корни найдены правильно. Возьмем многочлен третьей степени
. Найдем его корни тремя способами:

,

,

и символьными преобразованиями (результат на рис. 20).

Как видим, последний результат мало пригоден для использования, хотя и является «абсолютно» точным. Этот результат будет еще «хуже», если в многочлен добавить член с . Попробуйте с помощью символьных преобразований найти корни такого многочлена. Попробуйте с помощью символьных преобразований найти корни многочлена четвертой степени.

Символьные вычисления эффективны, если корни являются целыми или рациональными числами:

.

В этом примере символьные вычисления произведены с помощью панели Symbolic. Приведено также решение с помощью функции polyroots. Последние результаты менее эффектны, хотя с точки зрения вычислений ничем не хуже, так как разумный инженер округлит второй корень до числа – i .

Символьное нахождение корней можно применять и для уравнений, содержащих функции, отличные от многочленов:

.При использовании символьных вычислений следует быть осторожными. Так при нахождении нулей следующей функции МС14 выдает только одно значение: , хотя на промежутке
эта функция имеет 6 нулей:
. В более ранней версии системы (МС2000) указывались все нули.

Для полного ответа к ним нужно добавить число, кратное
.

Решим более сложную задачу. Функция y (x ) задана неявно уравнением
. Требуется построить график этой функцииy (x ) на отрезке .

Для решения этой задачи естественно воспользоваться функцией root. Однако она требует указания отрезка, на котором лежит искомый корень. Для этого найдем значение y графически при нескольких значениях x . (Графики приводятся ниже в виде отдельных рисунков, а не так как они размещены на экране MATHCAD).

Строим график (рис.21). На нем видно, что «разумные» значения y лежат в промежутке [– 5; 5]. Построим график в этом диапазоне. Изменения можно внести в шаблоны на имеющемся рисунке. Результат приведен на рис. 22. Видим, что корень лежит на отрезке . Возьмем следующее значение x . На бумаге – это новые записи, а на экране достаточно внести изменения в блоке, где x присваивается значение. При
получим рис.23. Согласно ему корень лежит на отрезке . При
получим рис. 24. Корень лежит на отрезке . В итоге можно ожидать, что корень при любыхx лежит на отрезке

Введем функцию пользователя .Построим график этой функции, считая переменным z , причем шаблоны по вертикальной оси можно не заполнять, система сама произведет масштабирование. График приведен на рис.25. По данному графику можно отследить значения функции с помощью панели X-Y Trace, как было описано выше.

Общий вид нелинейного уравнения

f (x )=0, (6.1)

где функция f (x ) – определена и непрерывна в некотором конечном или бесконечном интервале.

По виду функции f (x ) нелинейные уравнения можно разделить на два класса:

Алгебраические;

Трансцендентные.

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

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

Решить нелинейное уравнение – значит найти его корни или корень.

Всякое значение аргумента х , обращающее функцию f (x ) в нуль называется корнем уравнения (6.1) или нулем функции f (x ).

6.2. Методы решения

Методы решения нелинейных уравнений делятся на:

Итерационные.

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

Однако, встречающиеся на практике уравнения, не удается решить такими простыми методами, потому что

Вид функции f (x ) может быть достаточно сложным;

Коэффициенты функции f (x ) в некоторых случаях известны лишь приблизительно, поэтому задача о точном определении корней теряет смысл.

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

отделение корня , а именно, определение приближенного значения корня или отрезка, который содержит один и только один корень.

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

На первом этапе приближенное значение корня (начальное приближение ) может быть найдено различными способами:

Из физических соображений;

Из решения аналогичной задачи;

Из других исходных данных;

Графическим методом.

Более подробно рассмотрим последний способ. Действительный корень уравнения

f(x) =0

приближенно можно определить как абсциссу точки пересечения графика функции у= f (x ) с осью 0х. Если уравнение не имеет близких между собой корней, то этим способом они легко определяются. На практике часто бывает выгодным уравнение (6.1) заменить равносильным

f 1 (x)=f 2 (x)

где f 1 (x ) и f 2 (x ) – более простые, чем f (x ) . Тогда, построив графики функций f 1 (x ) и f 2 (x ), искомый корень (корни) получим как абсциссу точки пересечения этих графиков.

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

Если такие априорные оценки исходного приближения провести не удается, то находят две близко расположенные точки a , b , между которыми функция имеет один и только один корень. Для этого действия полезно помнить две теоремы.

Теорема 1. Если непрерывная функция f (x ) принимает значения разных знаков на концах отрезка [a , b ], то есть

f (a ) f (b )<0, (6.2)

то внутри этого отрезка находится, по меньшей мере, один корень уравнения.

Теорема 2. Корень уравнения на отрезке [a , b ] будет единственным, если первая производная функции f ’(x ), существует и сохраняет постоянный знак внутри отрезка, то есть

(6.3)

Выбор отрезка [a , b ] выполняется

Графически;

Аналитически (путем исследования функции f (x ) или путем подбора).

На втором этапе находят последовательность приближенных значений корня х 1 , х 2 , … , х n . Каждый шаг вычисления x i называется итерацией . Если x i с увеличением n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится.

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

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

Найденные приближенные значения корней можно уточнить с помощью различных итерационных методов. Рассмотрим три метода: 1) метод дихотомиии (или деление отрезка пополам); 2) метод простой итерации и 3) метод Ньютона.

Методы решения задачи

Метод деления отpезка пополам

Наиболее простым методом, позволяющим найти корень нелинейного уравнения (1), является метод половинного деления.

Пусть на отрезке задана непрерывная функция Если значения функции на концах отрезка имеют разные знаки, т.е. то это означает, что внутри данного отрезка находится нечетное число корней. Пусть для определенности корень один. Суть метода состоит в сокращении на каждой итерации вдвое длины отрезка. Находим середину отрезка (см. рис. 1) Вычисляем значение функции и выбираем тот отрезок, на котором функция меняет свой знак. Новый отрезок вновь делим пополам. И этот процесс продолжаем до тех пор, пока длина отрезка не сравняется с наперед заданной погрешностью вычисления корня. Построение нескольких последовательных приближений по формуле (3) приведено на рисунке 1.

Итак, алгоритм метода дихотомии:

1. Задать отрезок и погрешность.

2. Если f(a) и f(b) имеют одинаковые знаки, выдать сообщение о невозможности отыскания корня и остановиться.

Рис.1.

3. В противном случае вычислить c=(a+b)/2

4. Если f(a) и f(c) имеют разные знаки, положить b=c, в противном случае a=c.

5. Если длина нового отрезка, то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейти к шагу 3.

Так как за N шагов длина отрезка сокращается в 2 N раз, то заданная погрешность отыскания корня будет достигнута за итераций.

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

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

Свои способности человек может узнать, только попытавшись приложить их. (Сенека)

Численные методы: решение нелинейных уравнений

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

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

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

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

В простейшем случае у нас имеется функция , заданная на отрезке (a , b ) и принимающая определенные значения.

Каждому значению x из этого отрезка мы можем сопоставить число , это и есть функциональная зависимость, ключевое понятие математики.

Нам нужно найти такое значение при котором такие называются корнями функции

Визуально нам нужно определить точку пересечения графика функции с осью абсцисс.

Метод деления пополам

Простейшим методом нахождения корней уравнения является метод деления пополам или дихотомия .

Этот метод является интуитивно ясным и каждый действовал бы при решении задачи подобным образом.

Алгоритм состоит в следующем.

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

Поделим отрезок пополам и введем среднюю точку .

Тогда либо , либо .

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

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

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

К достоинствам метода деления пополам следует отнести его высокую надежность и простоту.

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

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

Метод Ньютона: теоретические основы

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

Уравнение касательной к функции в точке имеет вид:

В уравнении касательной положим и .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

Таким образом, сходимость метода касательных Ньютона очень быстрая.

Запомните этот замечательный факт!

Без всяких изменений метод обобщается на комплексный случай.

Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным.

Упражнение 1 . Найти с помощью метода касательных решение уравнения на отрезке (0, 2).

Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3).

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

Недостатком метода Ньютона является необходимость вычисления производных на каждом шаге.

Визуализация метода Ньютона

Метод Ньютона (метод касательных) применяется в том случае, если уравнение f (x ) = 0 имеет корень , и выполняются условия:

1) функция y = f (x ) определена и непрерывна при ;

2) f (a )· f (b ) < 0 (функция принимает значения разных знаков на концах отрезка [a ; b ]);

3) производные f" (x ) и f"" (x ) сохраняют знак на отрезке [a ; b ] (т.е. функция f (x ) либо возрастает, либо убывает на отрезке [a ; b ], сохраняя при этом направление выпуклости);

Основная идея метода заключается в следующем: на отрезке [a ; b ] выбирается такое число x 0 , при котором f (x 0 ) имеет тот же знак, что и f "" (x 0 ), т. е. выполняется условие f (x 0 )· f "" (x ) > 0 . Таким образом, выбирается точка с абсциссой x 0 , в которой касательная к кривой y = f (x ) на отрезке [a ; b ] пересекает ось Ox . За точку x 0 сначала удобно выбирать один из концов отрезка.

Рассмотрим метод Ньютона на конкретном примере.

Пусть нам дана возрастающая функция y = f(x) =x 2 -2, непрерывная на отрезке (0;2), и имеющая f " (x) = 2 x > 0 и f "" (x) = 2 > 0 .

Рисунок 1 . f(x) =x 2 -2

Уравнение касательной в общем виде имеет представление:

y-y 0 = f " (x 0)·(x-x 0).

В нашем случае: y-y 0 =2x 0 ·(x-x 0). В качестве точки x 0 выбираем точку B 1 (b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B 1 , и обозначаем точку пересечения касательной и оси Ox точкой x 1 . Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6.

Ox: x 1 =

Рисунок 2. Результат первой итерации

y=f(x) Ox через точку x 1 , получаем точку В 2 =(1.5; 0.25) . Снова проводим касательную к функции y = f(x) в точке В 2 , и обозначаем точку пересечения касательной и оси Ox точкой x 2 .

Уравнение второй касательной: y -0.25=2*1.5(x -1.5), y = 3 x - 4.25.

Точка пересечения касательной и оси Ox: x 2 = .

Рисунок 3. Вторая итерация метода Ньютона

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x 2 , получаем точку В 3 и так далее.

Рисунок 4. Третий шаг метода касательных

Первое приближение корня определяется по формуле:

= 1.5.

Второе приближение корня определяется по формуле:

=

Третье приближение корня определяется по формуле:

Таким образом, i -ое приближение корня определяется по формуле:

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства | xi - xi -1 | < e .

В нашем случае, сравним приближение, полученное на третьем шаге с реальным ответом, посчитанном на калькуляторе:

Рисунок 5. Корень из 2, посчитанный на калькуляторе

Как видно, уже на третьем шаге мы получили погрешность меньше 0.000002.

Таким образом можно вычислить значение величины "корень квадратный из 2" с любой степенью точности. Этот замечательный метод был изобретен Ньютоном и позволяет находить корни очень сложных уравнений.

Метод Ньютона: приложение на С++

В данной статье мы автоматизируем процесс вычисления корней уравнений, написав консольное приложение на языке C++. Разрабатывать его мы будем в Visual C++ 2010 Express, это бесплатная и очень удобная среда разработки С++.

Для начала запустим Visual C++ 2010 Express. Появится стартовое окно программы. В левом углу нажмем «Создать проект».

Рис. 1. Начальная страница Visual C++ 2010 Express

В появившемся меню выберем «Консольное приложение Win32», введем имя приложение «Метод_Ньютона».

Рис. 2. Создание проекта

Посмотрим, как это работает. Нажмем на зеленый треугольник в верхнем левом углу экрана, или же клавишу F5.

Если происходит ошибка компиляции «Ошибка error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден», то это лечится либо установкой первого Service pack 1, либо в настройках проекта Свойства -> Компоновщик отключаем инкрементную компоновку.

Рис. 4. Решение ошибки компиляции проекта

Мы будем искать корни у функции f(x) = x2-2 .

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

У нас появилось окно приложения:

Рис. 5. Ввод входных данных

Введем границы отрезка 3 и 5, и точность 0.05. Программа, как и надо, выдала сообщение об ошибке, что на данном отрезке корней нет.

Рис. 6. Ошибка «На этом отрезке корней нет!»

Выходить мы пока не собираемся, так что на сообщение «Exit?» вводим «0».

Теперь проверим работу приложения на корректных входных данных. Введем отрезок и точность 0.0001.

Рис. 7. Вычисление корня с необходимой точностью

Как мы видим, необходимая точность была достигнута уже на 4-ой итерации.

Чтобы выйти из приложения, введем «Exit?» => 1.

Метод секущих

Чтобы избежать вычисления производной, метод Ньютона можно упростить, заменив производную на приближенное значение, вычисленное по двум предыдущим точкам:

Итерационный процесс имеет вид:

Это двухшаговый итерационный процесс, поскольку использует для нахождения последующего приближения два предыдущих.

Порядок сходимости метода секущих ниже, чем у метода касательных и равен в случае однократного корня .

Эта замечательная величина называется золотым сечением:

Убедимся в этом, считая для удобства, что .

Таким образом, с точностью до бесконечно малых более высокого порядка

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

После подстановки имеем: и

Для сходимости необходимо, чтобы было положительным, поэтому .

Поскольку знание производной не требуется, то при том же объёме вычислений в методе секущих (несмотря на меньший порядок сходимости) можно добиться большей точности, чем в методе касательных.

Отметим, что вблизи корня приходится делить на малое число, и это приводит к потере точности (особенно в случае кратных корней), поэтому, выбрав относительно малое , выполняют вычисления до выполнения и продолжают их пока модуль разности соседних приближений убывает.

Как только начнется рост, вычисления прекращают и последнюю итерацию не используют.

Такая процедура определения момента окончания итераций называется приемом Гарвика.

Метод парабол

Рассмотрим трехшаговый метод, в котором приближение определяется по трем предыдущим точкам , и .

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

В форме Ньютона она имеет вид:

Точка определяется как тот из корней этого полинома, который ближе по модулю к точке .

Порядок сходимости метода парабол выше, чем у метода секущих, но ниже, чем у метода Ньютона.

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

Этот метод очень удобен для поиска корней многочленов высокой степени.

Метод простых итераций

Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки.

Пусть и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что).

По теореме Банаха существует и единственна неподвижная точка

Она может быть найдена как предел простой итерационной процедуры

где начальное приближение — произвольная точка промежутка .

Если функция дифференцируема, то удобным критерием сжатия является число . Действительно, по теореме Лагранжа

Таким образом, если производная меньше единицы, то является сжатием.

Условие существенно, ибо если, например, на , то неподвижная точка отсутствует, хотя производная равна нулю. Скорость сходимости зависит от величины . Чем меньше , тем быстрее сходимость.