Решение нелинейного уравнения общая постановка задачи

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

Раздел 2. Численные методы

Тема 1. Решение нелинейных уравнений с одной переменной

При решении ряда задач физики, механики и техники возникает необходимость решения уравнений с одной переменной. В общем случае нелинейное уравнение можно записать в виде: F(x)=0, где функция F(x) определена и непрерывна на промежутке . Корнем уравнения F(x)=0, является такое число c из области определения функции y=F(x), для которого справедливо равенство F(c)=0.

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

Задача численного решения уравнений состоит из двух этапов:

1. Отделение корней, т. е. нахождение достаточно малых окрестностей рассматриваемой области, в которых содержится единственный корень.

2. Уточнение корней, т. е. вычисление корней с заданной степенью точности в некоторой окрестности.

Во многих случаях отделение корней можно произвести графически. Для этого необходимо построить график функции y=F(x) и найти достаточно малые отрезки, содержащие по одной точке пересечения графика с осью ОХ. Иногда построение значительно упрощается, если функцию y=F(x) представить в виде f₁ (x)=f₂ (x) и найти отрезки оси ОХ, содержащие координаты х точек пересечения.

Отделение корней можно также произвести с помощью соответствующей компьютерной программы.

Пусть имеется уравнение F(x)=0, причем все интересующие вычислителя корни находятся на отрезке [A, B], на котором функция определена и непрерывна. Требуется отделить корни уравнения, т.е. найти отрезки [a, b] [A, B], содержащие по одному корню. Очевидно, что если на отрезке [a, b] функция меняет знак, то на этом отрезке находится, по крайней мере, один корень уравнения F(x)=0. Если длина отрезка [a, b] очень мала и F(a)*F(b) 0

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

Данный метод позволяет находить корни уравнения с заданной точностью е. Действительно, если на каком-то этапе процесса деления получен отрезок [a’, b’], содержащий корень, то приняв x≈(a’+b’)/2, мы найдем корень с точностью е(b’-a’)/2.

1.4. Уточнение корней методом итерации

Заменим уравнение F(x)=0 равносильным уравнением x=f(x). Пусть x* — искомый корень уравнения, а x₀ – полученное каким-либо способом грубо приближенное значение корня. Подставим x₀ в правую часть уравнения x=f(x), получим x₁ =f(x₀ ). Продолжая процесс подстановки, получим последовательность чисел: x₂ =f(x₁ ), x₃ =f(x₂ ),…, x_n =f(x_n-1 ). Такая последовательность называется последовательностью приближений или итерационной последовательностью.

Достаточное условие сходимости итерационного процесса

Пусть на отрезке [ a, b] уравнение x= f( x) имеет единственный корень и выполняются условия:

2. [ a, b] для всех х из [ a, b];

3. Существует такое действительное число q, что , для всех х из [ a, b];

Тогда итерационная последовательность x_n = f( x_n-1 ) сходится при любом начальном значении x₀ [ a, b].

Это условие не является необходимым, т.е. итерационная последовательность может сходиться и в том случае, если условия теоремы не выполняются.

Оценка погрешности метода итерации

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

1.5. Уточнение корней методом хорд

Пусть уравнение F(x)=0 имеет единственный корень на отрезке [a, b]. Если отрезок [a, b] достаточно мал, то можно считать, что функция y=F(x) монотонна на этом отрезке и не меняет направление выпуклости. Значит на отрезке [a, b] нет точек максимума и минимума, т.е. . Т.к. направление выпуклости не меняется то и . Получаем четыре вида графиков, которые объединяются в два типа.

I. тип. Условие: , где x- любая точка [a, b].

В рассмотренном выше случае для кривых I-го типа, правым концом всех проведенных хорд была точка В. Если, кривая относится ко II-му типу, то неизменным концом хорд будет точка А. Значит в формуле (1) b поменяется на а. Формула будет иметь вид:

Если на n-ом шаге, то считается, что необходимая точность е достигнута.

1.6. Уточнение корней методом касательных

При уточнении корней методом касательных все функции делятся на два типа, как и в методе хорд. Рассмотрим кривую I-го типа.

Проведем касательную к графику функции в точке В. Она пересечет ось ОХ в точке х_1. Через эту точку проведем прямую перпендикулярную оси ОХ до пересечения с графиком функции. Получим точку А₁ . Через неё опять проведем касательную. Получим точку х₂ . Продолжая этот процесс, получим последовательность х₁ , х₂ , х₃ , …,х_n, сходящуюся к х * .

Уравнение касательной к графику функции F(x)=0 в точке х=b имеет вид . Т.к. эта касательная пересекает ось ОХ в точке (х₁ , 0), то . Значит

Если, кривая относится ко II-му типу, то первую касательную к графику функции надо проводить в точке А и

Дальнейший расчет значений х₂ , х₃ , …,х_n не зависит от типа кривой и в обоих случаях вычисляется по формуле

Если на n-ом шаге, то считается, что необходимая точность е достигнута.

1.7. Уточнение корней комбинированным методом хорд и касательных

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

Метод реализуется по следующей схеме:

1. По методу хорд находят первое приближение корня .

2. По методу касательных находят . Если кривая относится к I-му типу, то . Если ко II-му типу, то .

3. По методу хорд .

4. По методу касательных .

Шаги 3 и 4 повторяются до тех пор, пока . Как только можно считать корень найденным .

Лабораторная работа №1. Решение нелинейных уравнений с одной переменной.

1. Сделать программу отделения корней уравнения F(x)=0 на [a, b] с шагом 0,5.

2. Сделать программы уточнения корней уравнения F(x)=0 на одном из отрезков, полученных в первой программе с точностью 0,001.

a) Методом половинного деления;

a) Методом итерации;

c) Методом касательных;

d) Комбинированным методом хорд и касательных.

Постановка задачи приближенного решения нелинейных уравнений (НЛУ). Этапы приближенного решения НЛУ

Одной из наиболее распространенных задач математического анализа является задача определения корней нелинейных уравнений (НЛУ) с одним неизвестным. Решение этой задачи имеет целый ряд важных практических приложений.

В общем виде нелинейное уравнение с одним неизвестным можно представить в виде (слайд 2):

f ( x ) = 0

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

В зависимости от вида функции f ( x ) различают алгебраические и трансцендентные уравнения. Алгебраическими уравненияминазываются уравнения, в которых функция f ( x ) представляет собой полином n-й степени (n > 1):

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

Решить НЛУ – означает найти его корни (слайд 3). Число x * называется корнем уравнения f ( x ) = 0, если при подстановке его в функцию f ( x ) она обращается в 0, а уравнение – в тождество.

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

найти приближенное решение НЛУ с погрешностью, не превышающей ε > 0, то есть удовлетворяющее неравенству

В существующих методах приближенного решения НЛУ предполагается, что известен отрезок [a;b], на котором находится один и только один корень уравнения. Для отыскания всех корней уравнения должно быть задано несколько таких отрезков, и отыскание каждого корня проводится независимо друг от друга. Поэтому приближенное решение НЛУ распадается на 2 этапа (слайд 4):

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

2) уточнение корней на каждом из полученных отрезков с наперед заданной точностью.

Уточнение корней производится итерационными методами, то есть путем построения последовательности приближений к корню x * : x ₀ , x ₁ , . x_n, … Если такая последовательностьпри n ® ¥ имеет предел, равный точному значению корня x * , то говорят, что итерационный процесс сходится. В качестве приближенного решения уравнения выбирается первое последовательное приближение x_k, попавшее в ε–окрестность корня x * .

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

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

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

На выходе мы получили траекторию полета снаряда, что дает нам ориентировочные представления о характеристиках орудия: при заданных параметрах мы получили дальность стрельбы чуть более 2,5 км и высоту подъема снаряда чуть выше 800 метров. Точнее мы сказать не можем, вернее можем, если с карандашиком по сетке определим координаты нужных точек на графике. Но это, как известно, не наш метод. Хорошо бы получить эти данные с точностью, обеспечиваемой используемыми нами инструментами и без ручного труда. Вот об этом мы сегодня и поговорим.

1. Постановка задачи

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

как функции времени. Высота полета снаряда это y(t). Если мы определим в какой момент времени высота становится равна нулю, то есть решим уравнение

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

Как найти максимальную высоту подъема снаряда? Из графика траектории видно, что по мере подъема снаряда его траектория становится всё более и более пологой, пока в экстремальной точке скорость на мгновение становится горизонтальной и дальше снаряд движется вниз.

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

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

Просто? Более чем.

2. Уравнение, которого нет

И вот тут котенка Гава, как известно, ждут неприятности. Начнем с того, что даже если уравнение задано в виде формулы (аналитически) не всегда удается найти его решение. Вот например

Как вам? Простенько, но попробуйте найти икс, используя всё то, чему вас учили в школе. То-то же…

Введем замену , тогда
\begin
&u \, e^ <2 — u>= 1 \\
&u \, e^ <-u>= e^ <-2>\\
&-u \, e^ <-u>= -e^ <-2>
\end
Пусть теперь , тогда

Теперь делаем финт ушами. Математики прошлого хорошо поработали за нас. Если задана функция вида

то обратная ей функция, называется W-функцией Ламберта.

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

откуда, раскручивая назад все замены получаем ответ

Приближенно этот ужас равен

Решение такого уравнения придется искать численно, тем более что очевидно его графическое решение

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

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

Создадим новый скрипт в том же каталоге, где расположены файлы ballistics.m, f.m и f_air.m. Назовем его, например cannon.m. Для начала зададимся параметрами снаряда, начальной скоростью и направлением выстрела

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

Обратите внимание, теперь в качестве моментов времени, передаваемых функции решения уравнения мы берем всего два значения: начальный момент времени (t = 0) и интересующий нас момент времени. Соответственно, переменная solv будет содержать два вектора фазовых координат: начальный и тот который нам нужен. Собираем все компоненты конечной точки фазовой траектории в вектор Y и возвращаем его значение из функции.

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

протестируем полученную функцию

При запуске скрипта на исполнение мы увидим в командном окне следующий вывод

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

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

3. Принципы численного решения нелинейных уравнений

Методы численного решения нелинейных и трансцендентных уравнений заточены под решение уравнений вида

К такой форме легко привести любое уравнение. Например

где . Корни этого, эквивалентного уравнения, равны корням исходного. Если мы построим график функции f(x), то увидим такую картинку

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

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

1. Поиск начального приближения корня
2. Уточнение корня с заданной погрешностью

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

Простейшим методом является метод простых итераций. Для применения этого метода уравнение преобразуют к виду

и выполняю расчеты по рекуррентной формуле

В нашем примере

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

Ага, видно, что начиная с шестой итерации четвертый знак получающегося числа остается неизменным. Значит мы нашли корень уравнения с погрешностью менее 10 -4 на шестой итерации.

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

Ограничимся членами первого порядка малости, заменив саму функцию f(x) касательной к её графику в точке x₀

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

Получаем итерационную формулу

В нашем примере

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

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

Эти примеры я привел, чтобы объяснить общий принцип. Кроме этих двух методов существует ещё масса методов, например:

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

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

4. Определяем параметры траектории пушечного ядра

Итак, найдем момент времени, когда снаряд упадет на землю. Прежде всего, определим интервал изоляции корня

Делаем это исходя из физического смысла задачи — после сразу выстрела высота полета снаряда неотрицательна. Перебираем все моменты времени, начиная от нуля, до тех пор, пока высота не станет отрицательна. Перебираем с достаточно крупным шагом (1 секунда) чтобы процедура не была слишком длительной, ведь на каждом шаге мы заново интегрируем дифференциальные уравнения движения, что весьма накладно сточки зрения вычислительных затрат. Как только высота станет отрицательной, заканчиваем перебор. Корень уравнения h(t) = 0 находится где-то внутри интервала [a, b]. Начальное приближение берем в середине этого интервала

Теперь отдаем уравнение на съедение процедуре решения нелинейных уравнений Octave

Функция fsolve() на вход принимает функцию, описывающую левую часть уравнения f(x) = 0 и значение начального приближения. Возвращает значение корня, вычисленное с заданной точностью. С какой точностью? Пока не будем задаваться этим вопросом и воспользуемся настройками по-умолчанию, на данном этапе они нас устраивают.

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

Аналогичным образом находим момент времени когда обнуляется вертикальная проекция скорости и вычисляем высоту полета снаряда в этот момент

В командном окне можно увидеть результаты работы программы

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

Для наших учебных целей точность вполне приемлема.