Классификация нелинейных уравнений и их решение

ПЛАН 1. ЛЕКЦИИ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ  1.1 Классификация уравнений и их решение. Особенности численных решений   1.2 Этап отделения корней 1.3 Уточнение корней. Итерационный процесс. Теорема Вейерштрасса  1.4 Метод деления отрезка пополам  1.5 Метод хорд  1.6 Метод простых итераций (Якоби)  1.7 Метод Ньютона (касательных)  1.8 Сравнительная характеристика методов 4 1.1 КЛАССИФИКАЦИЯ УРАВНЕНИЙ И ИХ ОСОБЕННОСТИ ЧИСЛЕННЫХ РЕШЕНИЙ РЕШЕНИЕ. Нелинейные уравнения с одним неизвестным, решение которых будет рассмотрено, имеют общий вид (1) f ( x)  0 , где f(x) – нелинейная функция аргумента x. При решении уравнений необходимо соблюдать этот канонический вид и приводить к нему рассматриваемые уравнения (справа должен быть 0), так как в конкретных методах работа проводится с полученной после этого функцией f(x). Например, заданное уравнение 5sin x  4 x 3  ln(2 x)  3 x  8 перед тем, как его решать, нужно привести к виду 5sin x  ln(2 x)  4 x 3  3 x  8  0 При этом функция из (1) представляет собой f ( x)  5sin x  ln(2 x)  4 x 3  3 x  8 с ней-то и производятся все действия. 6  Нелинейные функции вида f(x) подразделяются на алгебраические и трансцендентные (соответственно этому уравнения бывают алгебраические и трансцендентные). Алгебраические функции имеют каноническую форму полинома степени n : f ( x)  a0  a1 x  a2 x 2  a3 x 3  ...  an x n  (2) где – известные коэффициенты. К такому виду приводятся и некоторые другие функции, в частности – рациональные дроби. Трансцендентные функции (показательные, логарифмические, тригонометрические и др.) нельзя точно привести к каноническому виду. Такое деление нелинейных функций представляет собой математические нюансы и не имеет значения при решении уравнений численными методами. 7 Решить уравнение (1) f ( x)  0означает найти его корни. Корень уравнения – это число, при подстановке которого в уравнение оно превращается в тождество. Будем обозначать корень уравнения x*. При этом из формы уравнения (1) следует, что при x = x* функция обращается в нуль, т. е. график функции должен пересекать ось абсцисс (рис. 1). 8 Как уже отмечалось, нелинейные уравнения можно решить аналитически лишь в некоторых, немногих, случаях. С помощью численных же методов можно решить практически любые уравнения, причём существует довольно много этих методов и всегда можно подобрать наиболее оптимальный или перепроверить решение несколькими методами. При этом решения в отличие от аналитических методов полу- чаются приближёнными, однако всегда можно задать требуемую точность решения, что сводит на нет этот недостаток. Решение уравнений численными методами проходит в два этапа. Первый – отделение корней. На числовой оси выделяются достаточно узкие интервалы, содержащие корни. Второй – уточнение корней. В найденных интервалах конкретными методами отыскиваются корни с заданной точностью. 9 1.2 ЭТАП ОТДЕЛЕНИЯ КОРНЕЙ Абсолютно универсальных методов отделения корней, особенно для сложных функций, не существует. Всегда имеет место опасность пропустить тот или иной корень. Можно быть уверенным только в отношении элементарных функций, поведение которых хорошо известно: например, тригонометрические, показательные, логарифмические и другие функции. Самый простой, но и самый трудоёмкий – графический метод, т. е. построение графика функции y = f (x). В настоящее время при наличии компьютерных программ построения графиков это не представляет собой сложной задачи. Однако масштаб построения должен быть достаточно мелким, а интервал по оси x – достаточно большим, а это –два противоречивых требования. Лучше всего сначала построить график в широком интервале, а затем – в «подозрительных» местах, в более мелком масштабе. Часто эту задачу можно упростить, разбив заданную функцию f (x) на две более простые (или даже элементарные) функции (f 1 (x) и f 2 (x) ), т. е. сделав преобразование f ( x)  0  f1 ( x)  f 2 ( x) , а затем построив графики функций y1  f1 ( x) и y2  f 2 ( x) . Если функция y = f(x) имеет корень, то функции y1 и y2 будут пересекаться в точке, абсцисса которой будет совпадать с искомым корнем. 10 ПРИМЕР Если задано уравнение 3 0.5e0.6 x  1   0 x 0.5exp(0.6x) +1-3/x=0 то функцию слева можно разбить на две функции y1  0.5exp  0.6 x   1 и y2  3 / x и построить их графики (что довольно легко сделать по характеристическим точкам с пересчётом). Эти графики будут пересекаться в точке, абсцисса которой даст корень x* (рис. 2). 11 В результате использования того или иного графического метода можно отделить один или несколько корней с большой погрешностью: графики имеют точность максимум 2 – 3 значащие цифры. В качестве рабочих интервалов для уточнения корней выбирают интервалы с не-которым запасом, чтобы точно быть уверенным, что искомые корни будут в них входить. За концы интервалов принимают чаще всего узлы масштабной сетки или какие-то целые числа. Например, по рис. 2 можно выбрать интервал [1, 2]. Существуют также некоторые аналитические способы отделения корней. Результатом отделения корней должны быть чётко обозначенные интервалы; если уравнение имеет несколько корней, соответствующие интервалы не должны пересекаться или быть смежными, иначе методы уточнения корней могут работать некорректно. 12 1.3 УТОЧНЕНИЕ КОРНЕЙ. ИТЕРАЦИОННЫЙ ТЕОРЕМА ВЕЙЕРШТРАССА ПРОЦЕСС. Практически все методы уточнения корней являются итерационными методами, т. е. принадлежат к широкому классу численных методов вообще. Итерация – это последовательное приближение к чему-либо, в данном случае – к решению уравнения. В дальнейшем мы часто будем встречать итерационные методы в других областях вычислительной математики. Теоретически итерационный процесс бесконечен, поэтому всегда должна быть задана точность, с которой необходимо получить решение и по достижении которой нужно прекращать итерации. Чтобы реализовать итерационный процесс, необходимы четыре фактора: итерационная формула, критерий сходимости, начальное приближение и критерий окончания. 13 1. Итерационная формула. Она выводится из теоретических соображений; её наличие делает возможным сам итерационный процесс. 2. Критерий сходимости. Строго доказанное условие, гарантирующее сходимость итерационного процесса, т. е. его последовательное приближение к решению. Итерации могут и расходиться (удаляться от решения). 3. Начальное приближение. Позволяет начать итерационный процесс, так как последующее приближение к решению строится только на основе предыдущего приближения и необходимо с чего-то начинать. 4. Критерий окончания. Условие, позволяющее завершить итерационный процесс по достижении требуемой точности. Практическая реализация итерационных методов в конкретных языках программирования осуществляется с помощью итерационных циклов. В языке Pascal и современных языках на его основе – Delphi и Lasarus – таковыми являются операторы циклов repeat и while. 14 ТЕОРЕМА ВЕЙЕРШТРАССА Во многих методах решения нелинейных уравнений для построения итерационного процесса, т. е. в качестве итерационной формулы и критерия сходимости используется теорема Вейерштрасса. Теорема Вейерштрасса. Если на концах некоторого отрезка непрерывная функция f (x) принимает значения разных знаков, то на этом отрезке уравнение f (x) = 0 имеет хотя бы один корень. Если f (x) имеет первую производную f '(x) , не меняющую на этом отрезке знак, то существует только один корень уравнения. Для дальнейшего изложения необходимо напомнить, что функция f '(x), производная от функции f (x), или просто производная, определена (если она вообще существует) в конкретной точке x и численно равна тангенсу угла наклона касательной, проведённой к функции f (x) в точке x (рис. 3, 4, 5). Знак производной также определяется знаком тангенса угла наклона α (этот угол откладывается от горизонтали против часовой стрелки). Сама функция f '(x) представляет собой совокупность значений производной по всем точкам x (на рисунках показаны производные в одной произвольной точке x1). 15 16 17 18 Исходя из вышесказанного можно проиллюстрировать теорему Вейерштрасса следующим образом. Если функция f (x) монотонно убывает на отрезке [a, b] (или, наоборот – монотонно возрастает) и при этом пересекает ось x, (имеет корень x*), то функция от точки a будет лежать выше оси x, а функция от точки b – ниже этой оси, т. е. Функция будет менять знак на концах отрезка. При этом знак производной не меняется, т. е. наклон касательной α > 90º (рис. 6). Если же знак производной на отрезке [a, b] будет меняться, то возможно пересечение оси x большее количество раз (рис. 7). 19 20 21 Таким образом, первый этап – отделение корней – представляет собой предварительное математическое исследование для применения конкретных численных методов решения нелинейных уравнений. Рассмотрим четыре метода: 1) метод деления отрезка пополам, 2) метод хорд, 3) метод простых итераций Якоби 4) метод Ньютона. 22 1.4 МЕТОД ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ Другие названия метода: метод дихотомии, метод бисекций. Идея метода состоит в делении отрезка, содержащего корень, пополам; определении, в какой из двух половин останется корень, и отбрасывании ненужной половины. Затем процесс повторяется, т. е. в каждой следующей итерации уменьшается длина отрезка, содержащего корень. Итерации можно прекратить, когда эта длина станет ничтожной. Вместо итерационной формулы используется критерий наличия корня на отрезке, основанный на теореме Вейерштрасса. Если функция имеет на концах отрезка разные знаки (вне зависимости от того, возрастающая она или убывающая), это свидетельствует о наличии корня и произведение этих функций всегда будет отрицательным (см. рис. 1, 4): f(a)*f(b)=0. В методе исходный отрезок [a, b] делится пополам, берётся средняя на отрезке точка . Критерий можно применить к любому из двух отрезков, например – к левому: (a+b) / 2 23 Программно можно поставить такое условие (условный оператор) и в зависимости от его выполнения или невыполнения можно отбросить левый или правый отрезок. Отбрасывание отрезка программно означает перенос точки a в точку (a + b) / 2 для левого отрезка (это делается с помощью оператора присваивания) или перенос точки b в точку (a + b) / 2 для правого отрезка: a:=(a+b)/2 или b:=(a+b)/2. Таким образом проводится одна итерация. Начальным приближением метода служит исходный отрезок [a, b], полученный на этапе отделения корней. После каждой итерации длина отрезка уменьшается вдвое. В методе не требуется критерий сходимости, так как условие (3) обеспечивает нахождение корня. Как и в подавляющем большинстве итерационных методов, должна быть задана точность Ꜫ, с которой необходимо найти корень; по ней строится критерий окончания – итерации следует заканчивать, когда длина полученного отрезка [a, b] (лучше – по модулю) станет меньше заданной точности: При составлении программы (в данном пособии программы представлены на языке Pascal; для простоты применены комментарии, начинающиеся с «//», которых нет в классическом Pascal, но которые используются в Delphi или Lazarus) необходимо описать переменные, которые фигурируют в алгоритме, – концы отрезка [a, b], точность Ꜫ (заменяем на латинский эквивалент, например eps), искомый корень x, а также функцию f (x) с помощью function. Затем нужно ввести значения a, b, eps (так как они заданы) и организовать итерационный цикл уменьшения отрезка вдвое по критерию (3) с помощью оператора repeat или while. 24 Выход из итерационного цикла будет осуществляться по критерию (4). В качестве результата, т. е. значения корня, можно принять середину полученного отрезка. ТАКИМ ОБРАЗОМ, ПРОГРАММА МОЖЕТ ВЫГЛЯДЕТЬ ТАК: program dihotomia; //описание переменных a, b и eps, x можно не описывать, так как //он, как мы увидим ниже, в алгоритме участвовать не будет var a,b,eps: real; //описание заданной функции (например f), конкретный //вид функции не приведён function f(x:real):real; begin end; //начало основной программы begin //ввод исходных данных write('a='); readln(a); write('b='); readln(b); write('eps='); readln(eps); //итерационный цикл (например – repeat) repeat if f(a)*f((a+b)/2)<0 then b:=(a+b)/2 else a:=(a+b)/2; //выход из цикла по критерию (4) until abs(b-a) Купить от 250 ₽

Решение задач от ИИ за 2 минуты

Решить задачу

Найди решение своей задачи среди 1 000 000 ответов

Найти