Нахождение корней нелинейного уравнения. Решение нелинейных уравнений методом простых итераций - реферат Этапы численного решения нелинейных уравнений

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

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

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

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

Полное решение поставленной задачи можно разделить на 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 (
), целая часть соответствует номеру уравнения, остаток – номеру метода.

Уравнение типа F(x)=0 или x=f(x) называется нелинейным. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2; ...∞ корней. Рассмотренные ниже численные методы решения нелинейных уравнений позволяют находить один корень на заданном интервале . При этом на интервале должен существовать только один корень. Рассмотрим несколько методов решения нелинейных уравнений .

1. Метод перебора . При решении нелинейного уравнения методом перебора задаются начальное значение аргумента x=a и шаг h, который при этом определяет и точность нахождения корней нелинейного уравнения. Пока выполняется условие F(x)*F(x+h)>0 аргумент x увеличиваем на шаг h (x=x+h). Если произведение F(x)*F(x+h) становится отрицательным, то на интервале существует решение уравнения. Структограмма метода приведена на рисунке.

   
   

2. Метод половинного деления . При решении нелинейного уравнения методом половинного деления задаются интервал , на котором существует только одно решение, и желаемая точность ε. Затем определяется середина интервала с=(а+b)/2 и проверяется условие F(a)∙F(c)<0. Если указанное условие выполняется, то правую границу интервала b переносим в среднюю точку с (b=c). Если условие не выполняется, то в среднюю точку переносим левую границу(a=c). Деление отрезка пополам продолжается пока |b-a|>ε. Структограмма решения нелинейных уравнений методом половинного деления приведена на рисунке.

   Пока |b-a|>ε
   F(a)∙F(c)<0

   
   

   Рис. Структограмма для метода половинного деления

3. Метод хорд . При решении нелинейного уравнения методом хорд задаются интервал , на котором существует только одно решение, и точность ε. Затем через две точки с координатами (a,F(a)) и (b,F(b)) проводим отрезок прямой линии (хорду) и определяем точку пересечения этой линии с осью абсцисс (точка c). Если при этом F(a)∙F(c)<0, то правую границу интервала переносим в точку с (b=c). Если указанное условие не выполняется, то в точку c переносится левая граница интервала (а=с). Поиск решения прекращается при достижении заданной точности |F(c)|< ε. Для определения точки пересечения хорды с осью абсцисс воспользуемся следующей формулой (попытайтесь получить формулу самостоятельно).Структограмма метода хорд показана на рисунке.

   Пока |F(c)|>ε
   F(a)∙F(c)<0

   
   

   Рис. Структограмма для метода хорд

4. Метод касательных . При решении нелинейного уравнения методом касательных задаются начальное значение аргумента x 0 и точность ε. Затем в точке(x 0 ,F(x 0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x 1 . В точке (x 1 ,F(x 1)) снова строим касательную, находим следующее приближение искомого решения x 2 и т.д. Указанную процедуру повторяем пока |F(x i)| > ε. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой (получите формулу самостоятельно). Условие сходимости метода касательных F(x 0)∙F""(x 0)>0. Структограмма решения нелинейных уравнений методом касательных показана на рис.

   
   

5. Метод хорд-касательных . Если в методе касательных производную функции F"(x i) заменить отношением конечных приращений, то получаем расчетную формулу для метода хорд-касательных . Порядок выполнения вычислений в данном методе аналогичен рассмотренному ранее.
6. Метод итераций . При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x) . Задаются начальное значение аргумента x 0 и точность ε. Первое приближение решения x 1 находим из выражения x 1 =f(x 0), второе - x 2 =f(x 1) и т.д. В общем случае i+1 приближение найдем по формуле x i +1 =f(x i). Указанную процедуру повторяем пока |f(x i)|>ε. Условие сходимости метода итераций |f"(x)|<1. Структограмма метода итераций показана на рис.

   
   

Контрольное задание. Лабораторная работа 4.

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

Задание . Решить нелинейное уравнениеуказанными в табл. методами, предварительно определив интервал , на котором существует решение уравнения. Сделать проверку решения.

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

Варианты уравнений и методов их решения

1. Название, цель работы и задание.
2. Математическое описание, алгоритм (структограмма) и текст программы.
3. Результаты расчета, проверка и выводы по работе.

Для нахождения корня уравнения можно воспользоваться функцией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, как было описано выше.

Рассмотрим задачу нахождения корней нелинейного уравнения

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

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

Существование на найденном отрезке , по крайней мере, одного корня уравнения (1) следует из условия Больцано:

f(a)*f(b)<0 (2)

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

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

где вещественные коэффициенты.

• а) Уравнение степени n имеет n корней, среди которых могут быть как вещественные, так и комплексные. Комплексные корни образуют комплексно-сопряженные пары и, следовательно, уравнение имеет четное число таких корней. При нечетном значении n имеется, по меньшей мере, один вещественный корень.
• б) Число положительных вещественных корней меньше или равно числа переменных знаков в последовательности коэффициентов. Замена х на -х в уравнении (3) позволяет таким же способом оценить число отрицательных корней. итерация Ньютон дихотомия нелинейный

На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью. Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения. Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие:

где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях.

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

или малости невязки:

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

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

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 приближаются к истинному значению корня, то говорят, что итерационный процесс сходится.