Главная страница » Что является корнем нелинейного уравнения f x 0

Что является корнем нелинейного уравнения f x 0

  • автор:

6. Нелинейные уравнения#

Вычислительный аналог этой задачи мы определим следующим образом.

Пусть дана непрерывная функция \(f\) , и параметры \(\text\) и \(\text\) . Пусть корень уравнения \(f(x) = 0\) единственен и равен \(x = x^*\) .

Необходимо найти \(x = r\) такой, что выполнится либо гарантия локализации корня

либо гарантия малости функции

Первое условие подходит для методов, пользующихся тем, что непрерывная функция, имеющая разные знаки на концах отрезка \(f(a) f(b) < 0\) содержит корень \(x^* \in [a, b]\) . Второе условие подходит для остальных методов.

Для задачи поиска корня можно показать.

[ADJB17] Для дифференцируемой в корне \(x^*\) функции \(f\) число обусловленности задачи поиска корня \(f(x) = 0\) имеет вид

Также добавим, что в случае нескольких корней можно сначала найти первый корень \(x^*_1\) функции \(f\) , а затем продолжить поиск других корней, но уже для функции \(f(x)/(x-x^*_1)\) [89] . Кроме того, существуют процедуры по локализации корней функции, после чего задача сводится к поиску корня на каждом из интервалов по отдельности [PTVF07] .

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

§1. Постановка задачи. Основные определения. Рассмотрим нелинейное уравнение f(x)=0. Корнем этого уравнения называется значение , при котором . Решение уравнения заключается в нахождение его корней. Корень называется простым, если . Корень называется кратным, если . Целое число m называется кратностью корня , если для k=1,2,3. (m-1), а . Случай k=1 соответствует простому корню.

Рассмотрим график некоторой функции y=f(x) (xÎ[a,b]), который представлен на рис.1. Из определения следует, что корень является простым, если график функции y=f(x) пересекает ось 0x в точке под yглом a¹0 , и кратным, если он касается оси 0x в точке , т.к. имеем a=0.

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

Численное решение задачи нахождения корней нелинейного уравнения осуществляется в два этапа: этапа локализации корней и этапа итерационного уточнения корней.

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

Для локализации используются различные методы: аналитические, графические, таблицы. Аналитические и графические методы применяются для простых уравнений, например, для уравнения: . Для более сложных уравнений строятся таблицы и определяются значения xi и xl+I, при которых функция y=f(x) меняет знак (поиск простых корней), или производные меняют знак (поиск кратных корней). Отсюда сразу можно сделать вывод, что задача нахождения простых корней существенно проще, чем задача отыскания кратных корней.

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

В основе алгоритма лежит итерационная формула (название происходит от латинского слова “iteracio”-повторение). Для нахождения корня с точностью e используется та или иная итерационная формула. Итерационный метод называется одношаговым, если для вычисления очередного приближения xn используется только xn-1 приближение, и k–шаговым, если используются k предыдущих приближений: xn-1,xn-2,.. xnk.

Критерий сходимости. Для сходимости итерационного процесса необходимо и достаточно выполнение следующего условия:

где c и p — некоторые константы, число p называется порядком сходимости метода.

При p=1 и с<1, метод обладает линейной сходимостью. Если p>1, то имеем сверхлинейную сходимость, если p=2, то имеем квадратичную сходимость. Если для всех n выполняется условие: , где q<1, то говорят о сходимости со скоростью геометрической прогрессии.

Критерий окончания. Точное значение корня мы не знаем. Когда же закончить итерационный процесс, чтобы утверждать, что ?

Для каждого итерационного процесса существует свой критерий окончания в виде неравенства: где d(e)-функция от e, при выполнение которого всегда имеет место неравенство: .

§2. Метод Ньютона (метод касательных). Пусть корень локализован на отрезке [a,b]. Выбирается точка x0 на этом отрезке и в этой точке строится касательная к графику функции y=f(x). За новое приближение x1 принимается точка, в которой касательная пересекает ось 0x. Далее процесс повторяется. Таким образом, на каждом этапе решение исходного уравнения заменяется на решение линейного уравнения (уравнения касательной), т.е. проводится линеаризация исходного уравнения.

Запишем уравнение касательной в точке xn:

Полагая в, что при x=xn+1 имеем y=0 получаем формулу метода Ньютона:

Критерий окончания метода Ньютона:

§3. Метод Ньютона для системы нелинейных уравнений. Пусть имеется следующая система нелинейных уравнений:

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

где , i=1,2. n; а частные производные вычисляются в точке k-го приближения: x1=x1 ( k ) , x2=x2 ( k ) . xn=xn ( k ) .

Заменим в исходной системе нелинейные функции fi(x1,x2. xn) на правые части этих приближенных равенств, которые являются линейными функциями относительно переменных Dxi, i=1,2. n. В итоге получим следующую систему линейных уравнений относительно переменных Dxi, i=1,2. n:

Из этой системы можно определить значения Dxi, i=1,2. n и вычислить значения k+1-приближения: . Данная система уравнений представляют собой метод Ньютона для системы нелинейных уравнений.

Определитель этой системы называется якобианом.

Для существования решения якобиан должен быть отличен от нуля для каждого шага итерации.

Критерий окончания. Итерационный процесс продолжается до тех пор, пока не выполнятся условия: , для всех i=1,2. n.

Варианты задания №9

С помощью метода Ньютона решить следующую систему уравнений, результаты получить с точностью 0,1.

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

где f(x) — заданная алгебраическая или трансцендентная функция.

Решить уравнение — значит найти все его корни, то есть те значения x , которые обращают уравнение в тождество.
Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня xПP , которое отличается от точного значения корня x* на величину, по модулю не превышающую указанной точности (малой положительной величины) ε , то есть

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

Этапы приближенного решения нелинейных уравнений

Приближенное решение уравнения состоит из двух этапов:

  • Отделение корней, то есть нахождение интервалов из области определения функции f(x) , в каждом из которых содержится только один корень уравнения f(x)=0 .
  • Уточнение корней до заданной точности.

Отделение корней

Отделение корней можно проводить графически и аналитически.
Для того чтобы графически отделить корни уравнения, необходимо построить график функции f(x) . Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения.

Для примера рассмотрим задачу решения уравнения
Уравнение
где угол x задан в градусах. Указанное уравнение можно переписать в виде
f(x)=0
Для графического отсечения корней достаточно построить график функции

График функции
Из рисунка видно, что корень уравнения лежит в промежутке x∈(6;8) .

Аналитическое отделение корней

Аналитическое отделение корней основано на следующих теоремах.
Теорема 1 . Если непрерывная функция f(x) принимает на концах отрезка [a; b] значения разных знаков, т.е.
f(a)f(b)<0
то на этом отрезке содержится по крайней мере один корень уравнения.
Теорема 2 . Если непрерывная на отрезке [a; b] функция f(x) принимает на концах отрезка значения разных знаков, а производная f'(x) сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения f(x) = 0 .

Уточнение корней

Для уточнения корней может использоваться один из следующих методов:

Метод последовательных приближений (метод итераций)

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

Последовательность чисел x0, x1 ,…, xn называется итерационной , если для любого номера n>0 элемент xn выражается через элемент xn-1 по рекуррентной формуле
xn=f(xn-1)
а в качестве x0 взято любое число из области задания функции f(x) .

Реализация на C++ для рассмотренного выше примера
Уравнение
Уравнение может быть записано в форме
x=1/sinx

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

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

Если известно начальное приближение x0 корня уравнения f(x)=0, то последовательные приближения находят по формуле
метод Ньютона
Графическая интерпретация метода касательных имеет вид
Метод касательных
Реализация на C++
Для заданного уравнения
метод Ньютона
производная будет иметь вид f

Результат выполнения
Метод Ньютона

Метод секущих (метод хорд)

Если x0 , x1 — приближенные значения корня уравнения f(x) = 0 и выполняется условие
f(a)f(b)
то последующие приближения находят по формуле
Метод хорд
Методом хорд называют также метод, при котором один из концов отрезка закреплен, т.е. вычисление приближения корня уравнения f(x) = 0 производят по формулам:
Метод секущих
Геометрическая интерпретация метода хорд:
Метод хорд
Реализация на C++
В отличие от двух рассмотренных выше методов, метод хорд предполагает наличие двух начальных приближений, представляющих собой концы отрезка, внутри которого располагается искомый корень.

Результат выполнения
Реализация метода хорд

Метод половинного деления (метод дихотомии)

Если x0 , x1 — приближенные значения корня уравнения f(x) = 0 и выполняется условие
Метод половинного деления
то последующие приближения находятся по формуле
Метод дихотомии
и вычисляется f(xi) . Если f(xi)=0 , то корень найден. В противном случае из отрезков выбирается тот, на концах которого f(x) принимает значения разных знаков, и проделывается аналогичная операция. Процесс продолжается до получения требуемой точности.

Геометрическая интерпретация метода дихотомии
Метод дихотомии
Реализация на C++

Результат выполнения
Метод дихотомии
Для численного поиска решения также можно использовать генетические алгоритмы.

Методы решения нелинейного уравнения вида f x 0

В прошлой статье мы говорили о решении специальных типов уравнений с помощью точных методов. Сегодня же поговорим о приближенных (численных) методах решения уравнений вида f(x)=0.

В листингах программ есть записи вида:

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

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

Другие названия: метод бисекции (bisection method), метод дихотомии.

Метод половинного деления – простейший численный метод для решения нелинейных уравнений вида f(x)=0, где функция f(x) должна быть непрерывной на искомом отрезке [xL; xR], причем функция должна принимать значения разных знаков, т.е. должно выполняться условие:

С непрерывности функции f(x) следует, что на интервале [xL; xR] существует, по крайней мере, один корень уравнения (если их несколько, то метод находит один из них).

Выберем точку – середину интервала:

Если f(xM) = 0, то корень найден. Если f(x)≠0, то разобьем этот интервал на два: [xL; xM] и [xM; xR].

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

Геометрическая интерпретация метода:

Реализация метода на C#:

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

Другие названия: метод хорд (secant method);

Метод хорд – еще один численный метод для решения нелинейных уравнений вида f(x)=0, где функция f(x) должна быть непрерывной на искомом отрезке [x0; x1], причем функция должна принимать значения разных знаков, т.е. должно выполняться условие:

Последующие приближения находят по формуле:

Геометрическая интерпретация метода:

Реализация метода на C#:

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

Уравнение f(x)=0 с помощью некоторых преобразований необходимо переписать в виде x=φ(x).

Уравнение f(x)=0 эквивалентно уравнению x=x+λ(x)f(x) для любой функции λ(x)≠0. Возьмем φ(x)=x-λ(x)f(x) и выберем функцию (или переменную) λ(x)≠0 так, чтобы функция φ(x) удовлетворяла необходимым условиям.

Для нахождения корня уравнения x=φ(x) выберем некоторое начальное значение x0, которое должно находиться как можно ближе к корню уравнения. Дальше с помощью итерационной формулы xn+1=φ(xn) будем находить каждое следующее приближение корня уравнения.

Пример: x 2 -5x+6=0

Преобразования в вид x=φ(x):

Реализация метода на C#:

Метод Вегштейна

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

Это двухшаговый метод, и для начала вычислений необходимо задать 2 приближения xa и xb.

Реализация метода на C#:

public static double Wegstein(string expression, double xa, double xb, double epsilon = 0.00001) 0, если оно верно, то мы в качестве нового значения левого конца отрезка берем число c (т. к. это условие показывает, что корня на отрезке [a, c] нет), иначе оставляем значение a. Аналогично, для нового правого края отрезка мы проверяем истинность условия f(c)*f(b)>0, если оно верно, то мы в качестве нового значения правого конца отрезка берем число c (т. к. это условие показывает, что корня на отрезке [c, b] нет), иначе оставляем значение b. Функция ЕСЛИ копируется на группу ячеек в соответствующих столбцах.

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

Рисунок 4 – Снимок таблицы, реализующей метод деления отрезка пополам

Итак, одним из трех корней нелинейного уравнения x3 – 10x + 7=0, найденным с точностью e=0,0001, является x= — 3,46686. Как мы видим, он действительно принадлежит отрезку [-4; -3].

1.3.1 Алгоритм метода деления отрезка пополам

ЛЕКЦИЯ 3

1.4 Метод хорд

В этом методе нелинейная функция f(x) на отделенном интервале [а, b] заменяется линейной, в качестве которой берется хорда – прямая, стягивающая концы нелинейной функции. Эта хорда определяется как прямая, проходящая через точки с координатами (а, f(а)) и (b, f(b)). Имея уравнение хорды: у = cx + d, можно легко найти точку ее пересечения с горизонтальной осью, подставив в уравнение у = 0 и найдя из него x. Естественно, в полученной таким путем точке x1 не будет решения, ее принимают за новую границу отрезка, где содержится корень. Через эту точку с координатами (x1,f(x1)) и соответствующую границу предыдущего интервала опять проводят хорду, находят x2 и т. д. несколько раз, получая последовательность: х3, х4, х5 . сходящуюся к корню. Метод применим только для монотонных функций.

ВСТАВИТЬ ВЫВОД ФОРМУЛЫ И КАРТИНКУ!

Алгоритм метода зависит от свойств функции f(х). Если f(b) f»(x)>0, то строящаяся на каждом этапе хорда имеет правый фиксированный конец, и тогда алгоритм будет выглядеть так:

при этом последовательность х1, х2, х3. будет приближаться к корню слева x0=a.

Если f(a) f»(x) > 0, то строящаяся при каждом этапе хорда имеет левый фиксированный («закрепленный») конец и алгоритм выглядит следующим образом:

при этом последовательность х1, х2, x3. будет приближаться к корню справа x0=b.

Теоретически доказано, что если первые производные на концах интервала при монотонной и выпуклой функции f(x) не различаются более чем в 2 раза, то справедливо соотношение |хточн – хi| 0), или правая точка: x0 = b (если f(b) f»(х)>0). Алгоритм записывается следующим образом:

Алгоритм работоспособен при выпуклых и монотонных функциях f(x). Главным теоретическим достоинством метода является квадратичная скорость сходимости, что во многих случаях может привести к сокращению числа вычислений функции при получении решения с заданной погрешностью. В ряде случаев можно применять упрощенный алгоритм, связанный с сокращением числа повторений вычисления производных: вместо вычисления производной в каждой очередной точке f'(xi) использовать значение производной в начальной точке f'(x0). Видоизмененная формула:

Следует обратить внимание на следующую особенность метода: последовательность x1, x2, x3,… приближается к корню с другой стороны, в отличие от использования метода хорд при прочих равных условиях.

Отделить корни уравнения tg (0,55x+0,1) = x2 графически и уточнить один из них методом касательных с точностью до 0,001.

В предыдущем примере мы отделили один из корней и установили, что он принадлежит промежутку [0,6; 0,8]. Так как f (0,6) > 0, f (0,8) Q/2, где Q = max|f’(x)| на отрезке [a, b] и знак k совпадал бы со знаком f(x) на [a, b]. Итерационный процесс сходится при условии | y(x) |

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *