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

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

  • автор:

Численные методы решения нелинейных уравнений f(x)=0

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

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

Helpers.Function(expression, x)

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

public static double Bisection(string expression, double Left, double Right, double epsilon = 0.000001) < if (Helpers.Function(expression, Left) * Helpers.Function(expression, Right) >= 0) < throw new ArgumentException("F(a) and f(b) should have opposite signs."); >int iterationCount = 0; double c; do < c = (Left + Right) / 2; if (Helpers.Function(expression, Left) * Helpers.Function(expression, c) < 0) < Right = c; >else < Left = c; >if (Math.Abs(Helpers.Function(expression, c)) iterationCount++; > while (true); return c; >

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

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

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

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

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

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

public static double Secant(string expression, double xa, double xb, double epsilon = 0.00001) < double xlast; double x = 0; if (Helpers.Function(expression, xa) * Helpers.Function(expression, xb) >= 0) < throw new ArgumentException("F(a) and f(b) should have opposite signs."); >var iter = 0; do < xlast = x; x = xb - Helpers.Function(expression, xb) * (xb - xa) / (Helpers.Function(expression, xb) - Helpers.Function(expression, xa)); if (Helpers.Function(expression, x) * Helpers.Function(expression, xa) >0) < xa = x; >else < xb = x; >iter++; > while (Math.Abs(x — xlast) > epsilon || (xb — xa)

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

Уравнение 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#:

public static double SimpleIterations(string expression, double xa, double epsilon = 0.00001) < double x = 0.0; double xPrev = xa; var iter = 0; do < x = Helpers.Function(expression, xPrev); if (Math.Abs(x - xPrev) xPrev = x; iter++; > while (true); return x; >

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

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

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

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

public static double Wegstein(string expression, double xa, double xb, double epsilon = 0.00001) < double x = 0.0;

var iter = 0; do < x = xb - (xb - Helpers.Function(expression, xb)) / (1 - (Helpers.Function(expression, xb) - Helpers.Function(expression, xa)) / (xb - xa)); if (Math.Abs(x - xb) xa = xb; xb = x; iter++; > while (true); return x; >

Метод Ньютона

Если — начальное приближение корня уравнения f(x) = 0, то последовательные приближения находят по формуле:

Если f’ и непрерывны и сохраняют определенные знаки на отрезке , а f(a)f(b) < 0 , то, исходя из начального приближения удовлетворяющего условию можно вычислить с любой точностью единственный корень уравнения f(x) = 0.

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

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

public static double Newton(string expression, string derivativeExpression, double x, double epsilon = 0.00001) < int t = 0; double x1, y; do < t++; x1 = x - Helpers.Function(expression, x) / Helpers.Function(derivativeExpression, x); x = x1; y = Helpers.Function(expression, x); >while (Math.Abs(y) >= epsilon); return x; >

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

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

Решить уравнение — значит, найти все его корни, то есть те значения > , которые обращают уравнение в тождество.

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

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

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

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

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

Отделение корней можно проводить графически и аналитически.

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

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

Для примера рассмотрим задачу решения уравнения

где угол > задан в градусах.

Указанное уравнение можно переписать в виде

Для графического отсечения корней достаточно построить график функции

График функции sin(x)-1/x=0

Из рисунка видно, что корень уравнения лежит в промежутке >

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

Аналитическое отделение корней основано на следующих теоремах.

Теорема 1 . Если непрерывная функция > принимает на концах отрезка <\displaystyle<[a; b]>> значения разных знаков, т.е.

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

Теорема 2 . Если непрерывная на отрезке <\displaystyle<[a; b]>> функция > принимает на концах отрезка значения разных знаков, а производная > сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения > .

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

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

  • Метод последовательных приближений (метод итераций)
  • Метод Ньютона (метод касательных)
  • Метод секущих (метод хорд)
  • Метод половинного деления (метод дихотомии)

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

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

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

Функциональное уравнение может быть записано в виде

Функцию > называют сжимающим отображением .

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

а в качестве >> взято любое число из области задания функции > .

Реализация на C++ для рассмотренного выше примера

Уравнение может быть записано в форме

ЛП-01-02

1.2.6.Контрольные вопросы по теме «Методы решения нелинейных уравнений» 1. Что представляет собой нелинейное уравнение? 2. Что является корнем нелинейного уравнения f(x)=0 ? 3. Чему равна функция в точке корня? 4. Как называется процесс нахождения возможно более узкого отрезка, содержащего только один корень уравнения? 5. Каково условие существования на отрезке [a;b] хотя бы одного корня? 6. При каких условиях корень x будет единственным на отрезке [a;b] ? 7. Процесс решения нелинейного уравнения состоит из . этапов. 8. Как называются этапы решения нелинейного уравнения? 9. В чем заключается этап «отделения корней» нелинейного уравнения? 10. Что такое начальное приближение к корню? 11. Что определяется на этапе уточнения корней? 12. При каких условиях метод решения нелинейного уравнения сходится? 13. Какие методы не относятся к методам отделения корня? 14. Какие методы не относятся к методам уточнения корня? 15. Какие методы используются на этапе отделения корней? 16. Что необходимо, чтобы выбрать x 0 в качестве начального приближения в методе Ньютона? 17. Что является необходимым условием существования корня на отрезке [a;b] ? 18. Какой метод решения нелинейного уравнения требует более близкого к корню начального значения? 19. Что представляет собой метод решения нелинейного уравнения, в результате которого получается последовательность вложенных отрезков? 20. Можно ли уточнить корень уравнения графическим методом? 21. Что является первым приближением к корню, отделенному на отрезке [a;b], для решения нелинейного уравнения методом половинного деления? 22. На каком этапе применяется метод хорд? 23. При каких условиях метод половинного деления всегда находит корень уравнения f(x)=0 ? 24. Что означает термин — «метод расходится»? 25. Какой метод решения нелинейного уравнения обладает квадратичной сходимостью? 26. Каково правило выбора итерирующей функции при использовании метода итераций? 27. Что принимается за начальное приближение в методе итерации? 28. Каково правило выбора неподвижной точки при использовании метода хорд? 29. Какое значение выбирается в качестве начального приближения в методе хорд? 30. Какой метод не предназначается для решения нелинейных уравнений? 31. Как называется термин, который относится к методам решения нелинейных уравнений? 32. Почему необходим этап отделения корней? 33. При каких условиях метод хорд позволяет вычислить отделенный корень с заданной погрешностью? 34. В каких случаях за неподвижный конец отрезка [a;b] в методе хорд выбирают конец отрезка? 35. Для каких функций не рекомендуется применять метод Ньютона? 36. Что можно сказать о методе итерации, если на заданном отрезке имеются два корня? 37. Как могут осуществляться итерации приближения к корню в процессе решения уравнения методом простой итерации? 38. Какой метод решения нелинейного уравнения обладает свойством «самокоррекции»? 39. Что относится к способам улучшения сходимости метода простой итерации? Страница 20

03.05.2015 196.98 Кб 51 ЛИНИИ СВЯЗиии.docx

03.05.2015 1.84 Mб 28 Лк_1_ТелетрафикNGN 2013-03-05.pdf

03.05.2015 2.3 Mб 16 Лк_2_ТелетрафикNGN 2013-03-12.pdf

03.05.2015 647.85 Кб 19 Лк_4_ТелетрафикNGN 2013-03-26.pdf

03.05.2015 737.47 Кб 28 Лк_5_ТелетрафикNGN 2013-04-09.pdf

03.05.2015 617.6 Кб 6 ЛП-01-02.pdf

26.08.2019 331.78 Кб 2 ЛР 1 Аппаратура В-12-3.doc

01.09.2019 775.68 Кб 11 ЛР 9 методичка ВОСП СОПКА-3.doc

25.08.2019 287.23 Кб 3 ЛР-4-07.doc

19.11.2019 1.34 Mб 6 ЛР_30 Изучение отладочных средств цифровых сигн. doc

03.05.2015 205.13 Кб 18 ЛР_№26.pdf

Ограничение

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

Нелинейные системы и уравнения

Ищется решение нелинейного уравнения $$ \begin \tag f(x) = 0, \end $$ где \( f(x) \) — заданная функция. Корни уравнения (1) могут быть комплексными и кратными. Выделяют как самостоятельную проблему разделения корней, когда проводится выделение области в комплексной плоскости, содержащей один корень. После этого на основе тех или иных итерационных процессов при выбранном начальном приближении находится решение нелинейного уравнения (1).

В более общем случае мы имеем не одно уравнение (1), а систему нелинейных уравнений $$ \begin \tag f_i(x_1, x_2, \ldots, x_n) = 0, \quad i = 1, 2, \ldots n. \end $$ Обозначим через \( \mathbf = (x_1, x_2, \ldots, x_n) \) вектор неизвестных и определим вектор-функцию \( \mathbf(\mathbf) = (f_1(\mathbf), f_2(\mathbf), \ldots, f_n(\mathbf)) \). Тогда система (2) записывается в виде $$ \begin \tag \mathbf(\mathbf) = 0. \end $$ Частным случаем (3) является уравнение (1) (\( n = 1 \)). Второй пример (3) — система линейных алгебраических уравнений, когда \( \mathbf (\mathbf) = A \mathbf — \mathbf \).

Метод Ньютона

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

При итерационном решении уравнений (1), (3) задается некоторое начальное приближение, достаточно близкое к искомому решению \( x^* \). В одношаговых итерационных методах новое приближение \( x_ \) определяется по предыдущему приближению \( x_k \). Говорят, что итерационный метод сходится с линейной скоростью, если \( x_ — x^* = O(x_k — x^*) \) и итерационный метод имеет квадратичную сходимость, если \( x_ — x^* = O(x_k — x^*)^2 \).

В итерационном методе Ньютона (методе касательных) для нового приближения имеем $$ \begin \tag x_ = x_k + \frac, \quad k = 0, 1, \ldots, \end $$

Вычисления по (4) проводятся до тех пор, пока \( f(x_k) \) не станет близким к нулю. Более точно, до тех пор, пока \( |f_(x_k)| > \varepsilon \), где \( \varepsilon \) — малая величина.

Простейшая реализация метода Ньютона может выглядеть следующим образом:

def naive_Newton(f, dfdx, x, eps): while abs(f(x)) > eps: x = x - float(f(x))/dfdx(x) return x

Чтобы найти корень уравнения \( x^2 = 9 \) необходимо реализовать функции

def f(x): return x**2 - 9 def dfdx(x): return 2*x print naive_Newton(f, dfdx, 1000, 0.001)

Данная функция хорошо работает для приведенного примера. Однако, в общем случае могут возникать некоторые ошибки, которые нужно отлавливать. Например: пусть нужно решить уравнение \( \tanh(x) = 0 \), точное решение которого \( x = 0 \). Если \( |x_0| \leq 1.08 \), то метод сходится за шесть итераций.

-1.0589531343563485 0.9894042072982367 -0.784566773085775 0.3639981611100014 -0.03301469613719421 2.3995252668003453e-05 Число вызовов функций: 25 Решение: 3.0000000001273204

Теперь зададим \( x_0 \) близким к \( 1.09 \). Возникнет переполнение

-1.0933161820201083 1.104903543244409 -1.1461555078811896 1.3030326182332865 -2.064923002377556 13.473142800575976 -126055892892.66042

Возникнет деление на ноль, так как для \( x_7 = -126055892892.66042 \) значение \( \tanh(x_7) \) при машинном округлении равно \( 1.0 \) и поэтому \( f^\prime(x_7) = 1 — \tanh(x_7)^2 \) становится равной нулю в знаменателе.

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

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

  1. обрабатывать деление на ноль
  2. задавать максимальное число итераций в случае расходимости метода
  3. убрать лишний вызов функции f(x)
def Newton(f, dfdx, x, eps): f_value = f(x) iteration_counter = 0 while abs(f_value) > eps and iteration_counter  100: try: x = x - f_value/dfdx(x) except ZeroDivisionError as err: print("Ошибка: <>".format(err)) sys.exit(1) f_value = f(x) iteration_counter += 1 if abs(f_value) > eps: iteration_counter = -1 return x, iteration_counter

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

При реализации метода Ньютона нужно знать аналитическое выражение для производной \( f^\prime(x) \). Python содержит пакет SymPy, который можно использовать для создания функции dfdx . Для нашей задачи это можно реализовать следующим образом:

from sympy import symbol, tanh, diff, lambdify x = symbol.Symbol('x') # определяем математический символ x f_expr = tanh(x) # символьное выражение для f(x) dfdx_expr = diff(f_expr, x) # вычисляем символьно f'(x) # Преобразуем f_expr и dfdx_expr в обычные функции Python f = lambdify([x], # аргумент f f_expr) dfdx = lambdify([x], dfdx_expr) tol = 1e-1 sol, no_iterations = Newton(f, dfdx, x=1.09, eps=tol) if no_iterations > 0: print("Уравнение: tanh(x) = 0. Число итераций: <>".format(no_iterations)) print("Решение: <>, eps = <>".format(sol, tol)) else: print("Решение не найдено!") def F(x): y = np.zeros_like(x) y[0] = (3 + 2*x[0])*x[0] - 2*x[1] - 3 y[1:-1] = (3 + 2*x[1:-1])*x[1:-1] - x[:-2] - 2*x[2:] -2 y[-1] = (3 + 2*x[-1])*x[-1] - x[-2] - 4 return y def J(x): n = len(x) jac = np.zeros((n, n)) jac[0, 0] = 3 + 4*x[0] jac[0, 1] = -2 for i in range(n-1): jac[i, i-1] = -1 jac[i, i] = 3 + 4*x[i] jac[i, i+1] = -2 jac[-1, -2] = -1 jac[-1, -1] = 3 + 4*x[-1] return jac n = 10 guess = 3*np.ones(n) sol, its = Newton_system(F, J, guess) if its > 0: print("x = <>".format(sol)) else: print("Решение не найдено!")

Решение нелинейных систем

Идея метода Ньютона для приближенного решения системы (2) заключается в следующем: имея некоторое приближение \( \pmb^ \), мы находим следующее приближение \( \pmb^ \), аппроксимируя \( \pmb(\pmb^) \) линейным оператором и решая систему линейных алгебраических уравнений. Аппроксимируем нелинейную задачу \( \pmb(\pmb^) = 0 \) линейной $$ \begin \tag \pmb(\pmb^) + \pmb(\pmb^)(\pmb^ — \pmb^) = 0, \end $$ где \( \pmb(\pmb^) \) — матрица Якоби (якобиан): $$ \pmb(\pmb^) = \begin \frac<\partial f_1(\pmb^)> <\partial x_1>& \frac<\partial f_1(\pmb^)> <\partial x_2>& \ldots & \frac<\partial f_1(\pmb^)> <\partial x_n>\\ \frac<\partial f_2(\pmb^)> <\partial x_1>& \frac<\partial f_2(\pmb^)> <\partial x_2>& \ldots & \frac<\partial f_2(\pmb^)> <\partial x_n>\\ \vdots & \vdots & \ldots & \vdots \\ \frac<\partial f_n(\pmb^)> <\partial x_1>& \frac<\partial f_n(\pmb^)> <\partial x_2>& \ldots & \frac<\partial f_n(\pmb^)> <\partial x_n>\\ \end $$ Уравнение (5) является линейной системой с матрицей коэффициентов \( \pmb \) и вектором правой части \( -\pmb(\pmb^) \). Систему можно переписать в виде $$ \pmb(\pmb^)\pmb = — \pmb(\pmb^), $$ где \( \pmb = \pmb^ — \pmb^ \).

Таким образом, \( k \)-я итерация метода Ньютона состоит из двух стадий:

1. Решается система линейных уравнений (СЛАУ) \( \pmb(\pmb^)\pmb = -\pmb(\pmb^) \) относительно \( \pmb \).

2. Находится значение вектора на следующей итерации \( \pmb^ = \pmb^ + \pmb \).

Для решения СЛАУ можно использовать приближенные методы. Можно также использовать метод Гаусса. Пакет numpy содержит модуль linalg , основанный на известной библиотеке LAPACK, в которой реализованы методы линейной алгебры. Инструкция x = numpy.linalg.solve(A, b) решает систему \( Ax = b \) методом Гаусса, реализованным в библиотеке LAPACK.

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

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

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

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