Графическое решение уравнений

 

Действительные корни уравнения f(x) = 0 приближенно можно определить как абсциссы точек пересечения графика функции y = f(x) с осью ОХ (см. рис. 4.1, а). На практике часто бывает удобнее уравнение (4.1) заменить равносильным ему уравнением

 

, (4.2)

 

где функции φ (x)и ψ (x) более простые, чем функция f(x ). Тогда, построив графики этих функций, искомые корни получим как абсциссы точек пересечения этих графиков (смотри рис. 4.1, б).

 

 

 

 

а ) б )

Рис. 4.1. Графический метод нахождения корней уравнения.

 

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

Сформулируем без доказательства очень важную для рассмотрения дальнейших вопросов теорему.

 

Теорема: Если непрерывная функция f(x) принимает значения разных знаков на концах отрезка [α, β ], то есть f(α )·f(β ) < 0, то внутри этого отрезка содержится по меньшей мере один корень уравнения f(x) = 0, а именно: найдётся хотя бы одно число такое, что f(ξ ) = 0.

 

Пусть дано уравнение

 

f(x) = 0 , (4.3)

 

где функция f(x) определена и непрерывна на интервале [a, b] и f(a)·f(b) < 0. Для нахождения корня уравнения делим отрезок [a, b] пополам:

· если f((a + b)/2) = 0, то ξ = (a + b)/2 является корнем уравнения (4.3);

· если , то выбираем ту половину отрезка [a, (a + b)/2] или [(a + b)/2, b], на концах которого функция f(x) имеет противоположные знаки. Новый суженный отрезок [a₁, b₁] снова делим пополам и проводим тот же анализ и т.д.

Очевидно, что закончить уточнение значения корня можно при достижении условия |а_j – b_j| < ε , где ε > 0 - сколь угодно малое число. Второй способ закончить вычисления - задать максимальное значение невязки:
f((a_j + b_j)/2) < ε.

 

Замечания

 

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

· Как недостаток метода можно отметить его медленную сходимость (за один шаг интервал, где находится корень, сужается всего в два раза).

 

Метод хорд

 

Пусть дано уравнение

 

f(x) = 0 , (4.4)

 

где функция f(x)определена и непрерывна на интервале [a, b] и выполняется соотношение f(a)·f(b) < 0.

Пусть для определенностиf(a) < 0, f(b) > 0. Тогда вместо того, чтобы делить отрезок [a, b] пополам, более естественно разделить его в отношении
- f(a): f(b). При этом новое значение корня определяется из соотношения

 

x₁ = a + h₁, (4.5)

где

. (4.6)

Далее этот прием применяем к одному из отрезков[a, x₁] или [x₁, b], на концах которого функция f(x) имеет противоположные знаки. Аналогично находим второе приближение x₂ и т.д. (см. рис. 4.2.).

Геометрически этот способ эквивалентен замене кривойy = f(x) хордой, проходящей через точкиА(a, f(a)) и B(b, f(b)).

 

 

Рис. 4.2. Уточнение корня уравнения методом хорд

Действительно, уравнение хорды АВ имеет вид

 

(4.7)

 

Учитывая, что при х = х₁ => y = 0, получим

(4.8)

 

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

1. Из рис. 4.2, a видно, что неподвижна точка а, а точкаb приближается к ξ, то есть

(4.9)

 

Преобразовав выражение (4.9), окончательно получим

 

(4.10)

 

2. Из рис. 4.2, bвидно, что точкаb остается неподвижной, а точкаа приближается к ξ, тогда вычислительная формула примет вид

 

(4.11)

 

Таким образом, для вычисления корня уравнения имеем две различные вычислительные формулы (4.10) и (4.11).

Какую точку брать за неподвижную?

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

 

f(x)·f”(x) > 0. (4.12)

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

Пусть корень ξ уравнения

f(x) = 0, (4.13)

 

отделен на отрезке [a, b], причем первая и вторая производные f¢ (x) и f¢ ¢ ( x) непрерывны и сохраняют определенные знаки при . Найдя какое-нибудь n-ое приближение корня , мы можем уточнить его по методу Ньютона следующим образом. Пусть

 

ξ = x_n + h_n, (4.14)

 

где h_n - величина малая. Отсюда по формуле Тейлора получим (ограничиваясь первым порядком малости относительно h_n)

 

f(x_n + h_n) = f(x_n) + h_n f¢ (x_n) = 0. (4.15)

 

Следовательно,

 

h_n = - f(x_n) / f¢ (x_n). (4.16)

 

Подставив полученное выражение в формулу (4.14), найдем следующее (по порядку) значение корня:

 

(4.17)

 

Проиллюстрируем графически нахождение корня методом Ньютона (рис. 4.3.).

 

 

Рис. 4.3. Уточнение корня методом касательных

 

Если вкачестве начального приближения выбрать точкух₀ = В₀, то процесс быстро сходится. Если же выбрать точку х₀ = А₀, то х₁ [ a, b ], и процесс нахождения корня расходится. Рекомендуется: в качествех₀ выбрать точку, где f(x)·f¢ ¢ (x) > 0.

Комбинированный метод

 

Пусть f(a)·f(b) < 0, а f¢ (x) и f¢ ¢ (x) сохраняют постоянные знаки на отрезке [a¸ b]. Соединяя метод хорд и метод касательных, получаем метод, на каждом шаге которого находим значения по недостатку и значения по избытку точного корня ξ уравненияf(x) = 0. Теоретически здесь возможны четыре случая:

 

· f¢ (x) > 0; f¢ ¢ (x) > 0;

· f¢ (x) > 0; f¢ ¢ (x) < 0;

· f¢ (x) < 0; f¢ ¢ (x) > 0;

· f¢ (x) < 0; f¢ ¢ (x) < 0.

 

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

Итак, пусть f¢ (x) > 0 и f¢ ¢ (x) > 0при . Полагаем, что (для метода хорд), (для метода касательных). Тогда новые значения корня вычисляем по формулам

(4.18)

 

Рис. 4.4 наглядно иллюстрирует суть комбинированного метода.

 

Рис. 4.4. Уточнение корня комбинированным методом

 

Доказано, что . Следует обратить внимание на то, что на каждом шаге метод хорд применяется к новому отрезку . Если задать максимальное значение погрешности ε > 0, процесс уточнения значения корня продолжаем до тех пор, пока не выполнится условие

 

. (4.19)

 

Пример 4.1. Вычислить с точностью до 0.0005 положительный корень уравнения

f(x) = x⁵ – x – 0.2 = 0.

 

На первом этапе отделения корней выбрали интервал [1.0, 1.1], на концах которого функция имеет противоположные знаки. Действительно,
f(1) = – 0.2 < 0, f(1.1) = 0.31051 > 0. В выбранном нами интервале f¢ ¢ (x) > 0, f¢ ¢ (x) > 0, то есть знаки производных сохраняются.

Применим комбинированный метод, приняв . По формулам (4.18) вычислим

.

 

Так как точность недостаточная (погрешность велика), вычислим следующие значения:

 

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

Замечания

· Комбинированный метод наиболее трудоемок.

· Метод, как и метод Ньютона не всегда сходится (почему? ).

· Комбинированный метод сходится быстрее всех ранее рассмотренных, (если он сходится).

 

Вопросы для самопроверки

 

· Какие точные методы решения нелинейных уравнений вы знаете?

· Для чего нужен первый этап - отделение корней?

· Сформулируйте условия существования решения уравнения. Являются ли эти требования необходимыми и достаточными?

· Что можно сказать о точности методов половинного деления, хорд, касательных и комбинированного? По каким параметрам их еще можно сравнить?

· В соответствии с известной теоремой на отрезке [ a, b ] существует решение. Всегда ли его можно найти методом половинного деления, методом хорд, и т.п.?

 

 

5. Приближенное решение
систем нелинейных уравнений

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

Рассмотрим нелинейную систему уравнений

 

(5.1)

 

с действительными левыми частями. Систему (5.1) можно представить в матричном виде

(5.2)

 

Здесь приняты следующие обозначения:

 

- вектор аргументов, а - вектор – функция.

 

Для решения системы (5.2) воспользуемся методом последовательных приближений. Предположим, что найдено р-ое приближение x_p = (x₁^(p), x₂^(p), ..., x_n^(p))одного из изолированных корней x = (x₁, x₂, x₃, ..., x_n) векторного уравнения (5.2). Тогда точный корень уравнения (5.2) можно представить в виде

(5.3)

где - поправка (погрешность) корня на n – ом шаге.

Подставив выражение (5.3) в (5.2), получим

 

(5.4)

 

Предположим, что функция f(x) - непрерывно дифференцируема в некоторой выпуклой области, содержащей x и x^{(p )}. Тогда левую часть уравнения (5.4) разложим в ряд Тейлора по степеням малого вектора ε ^{(p )}, ограничиваясь линейными членами:

 

, (5.5)

 

или в развернутом виде:

 

(5.6)

Из анализа формул (5.5) и (5.6) следует, что под производной f¢ (x) следует понимать матрицу Якоби системы функций f_1, f_{2, ...,} f_n, относительно переменных x₁, x₂, x₃, ..., x_n, то есть:

 

. (5.7)

 

Выражение (5.7) в краткой записи можно представить:

 

(5.8)

 

Выражение (5.6) представляет собой линейную систему относительно поправок (i = 1, 2, ..., n) с матрицей W(x), поэтому формула (5.5) может быть записана в следующем виде:

 

(5.9)

 

Отсюда, предполагая, что матрица W(x^(p)) - неособенная, получим:

 

(5.10)

 

Теперь, подставив выражение (5.10) в формулу (5.3), окончательно получим:

(5.11)

 

Таким образом, получили вычислительную формулу (метод Ньютона), где в качестве нулевого приближения x⁽⁰⁾ можно взять приближенное (грубое) значение искомого корня.

 

Пример 5.1. Рассмотрим применение метода Ньютона на примере системы двух нелинейных уравнений

 

(5.12)

 

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

 

 

Здесь A, B, C, D – функционалы от переменных x_1, x_2. Нас фактически интересует W^{- 1} . Пусть матрица W- неособенная, тогда обратная матрица вычисляется

 

Теперь вернемся к системе (5.12). Графическое решение этой системы дает две точки пересечения: М₁ (1.4; -1.5) и М₂ (3.4; 2.2). Зададим начальное приближение:

 

 

 

Используя формулу (5.11), получим:

 

 

Аналогично получим:

 

 

5.2. Метод градиента (метод скорейшего спуска)

 

Пусть имеется система нелинейных уравнений:

 

(5.13)

 

Систему (5.13) удобнее записать в матричном виде:

 

(5.14)

 

где - вектор – функция; - вектор – аргумент.

 

Решение системы (5.14), как и для системы линейных уравнений (см. п. 3.8), будем искать в виде

 

(5.15)

Здесь и - векторы неизвестных на p и p + 1 шагах итераций; вектор невязок на p-ом шаге – f^(p) = f(x^(p)); W'_p – транспонированная матрица Якоби на p– ом шаге;

 

;

 

.

 

Пример 5.2. Методом градиента вычислим приближенно корни системы

 

 

расположенные в окрестности начала координат.

 

Имеем:

 

Выберем начальное приближение:

 

 

По вышеприведенным формулам найдем первое приближение:

 

 

 

Аналогичным образом находим следующее приближение:

 

 

 

Ограничимся двумя итерациями (шагами), и оценим невязку:

 

 

Замечания

· Как видно из примера, решение достаточно быстро сходится, невязка быстро убывает.

· При решении системы нелинейных уравнений методом градиента матрицу Якоби необходимо пересчитывать на каждом шаге (итерации).

 

Вопросы для самопроверки

 

· Как найти начальное приближение: а) для метода Ньютона; б) для метода градиента?

· В методе скорейшего спуска вычисляется Якобиан (матрица Якоби). Чем отличается Якобиан, вычисленный для СЛАУ, от Якобиана, вычисленного для нелинейной системы уравнений?

· Каков критерий остановки итерационного процесса при решении системы нелинейных уравнений: а) методом Ньютона; б) методом скорейшего спуска?

6. Решение обыкновенных
дифференциальных уравнений

 

Методы решения задачи Коши

 

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

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

Пусть на отрезке x₀ £ x £ b требуется найти решение y(x) дифференциального уравнения

, (6.1)

 

удовлетворяющее при x = x₀ начальному условию

(6.2)

Будем считать, что условия существования и единственности решения поставленной задачи Коши выполнены.

На практике найти общее либо частное решение задачи Коши удается крайне редко, поэтому приходится решать эту задачу приближенно. Отрезок [x_0, b] накрывается сеткой (разбивается на интервалы) чаще всего с постоянным шагом h ( h = x_n+1 - x_n ), и по какому-то решающему правилу находится значение y_n+1 = y(x_n+1). Таким образом, в качестве решения задачи Коши численными методами мы получаем таблицу, состоящую из двух векторов:
x = (x₀ , x_{1, …}x_n) – вектора аргументов и соответствующего ему вектора функции y = ( y_0, y₁, _… y_n ).

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

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

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

 

(6.3)

 

Здесь а значения i = 2, 3, …m находят по формулам, полученным последовательным дифференцированием уравнения (6.1):

 

(6.4)

 

Для значений x, близких к x ₀, метод рядов (6.3) при достаточно большом значении m дает обычно хорошее приближение к точному решению y(x) задачи (6.1). Однако с ростом расстояния ê x - x₀ê погрешность приближенного равенства y(x) » y_m(x), вообще говоря, возрастает по абсолютной величине, и правило (6.3) становится вовсе неприемлемым, когда x выходит из области сходимости соответствующего ряда (6.3) Тейлора.

Если в выражении (6.3) ограничиться m = 1, то для вычисления новых значений y(x) нет необходимости пересчитывать значение производной, правда и точность решения будет невысока. Графическая интерпретация этого метода приведена на рис. 6.1.

 

 

 

Рис. 6.1. Разложение функции в ряд Тейлора (m=1)

 

6.2. Метод рядов, не требующий вычисления производных
правой части уравнения

 

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

(6.5)

где x_n+1 = x_n + h.

Чтобы выполнить это условие (последнее), производные y⁽ⁱ⁾(x) ,
i = 2, 3,..., m, входящие в правую часть уравнения (6.5), можно заменить по формулам численного дифференцирования их приближенными выражениями через значение функции y' и учесть, чтоy'(x) = f [x, y(x)].

В случае m = 1 приближенное равенство (6.5) не требует вычисления производных правой части уравнения и позволяет с погрешностью порядка h² находить значение y(x_n+ h) решения этого уравнения по известному его значению y(x_n). Соответствующее одношаговое правило можно записать в виде

(6.6)

 

Это правило (6.6) впервые было построено Эйлером и носит его имя. Иногда его называют также правилом ломаных или методом касательных. Метод Эйлера имеет простую геометрическую интерпретацию (см. рис. 6.2).

 

 

 

 

Рис. 6.2. Нахождение решения методом Эйлера

Замечание Метод Эйлера имеет порядок точности ~ h² на одном шаге. Практическая оценка погрешности приближенного решения может быть получена по правилу Рунге.

 

Метод Рунге-Кутта

 

Изложим идею метода на примере задачи Коши:

 

(6.7)

 

Интегрируя это уравнение в пределах от x до x + h (0 < h < 1), получим равенство

(6.8)

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

Для удобства записи выражения (6.8) используем обозначение
∆ y = y(x + h) – y(x) и замену переменной интегрирования t = x + ah. Окончательно получим:

(6.9)

Указав эффективный метод приближенного вычисления интеграла в выражении (6.9), мы получим при этом одно из правил численного интегрирования уравнения (6.7).

Постараемся составить линейную комбинацию величин j _i,
i = 0, 1, ..., q, которая будет являться аналогом квадратурной суммы и позволит вычислить приближенное значение приращения Dy:

 

(6.10)

где

Метод четвертого порядка для q = 3, являющийся аналогом широко известной в литературе четырехточечной квадратурной формулы " трех восьмых", имеет вид

(6.11)

где

 

Особо широко известно другое вычислительное правило типа Рунге-Кутта четвертого порядка точности:

(6.12)

где

 

Метод Рунге-Кутта имеет погрешность четвертого порядка ( ~ h ⁴ ).

 

Правило Рунге. Если приближенный метод имеет порядок погрешности m, то погрешность можно приближенно оценить по формуле

 

(6.13)

 

В формуле (6.13) O(x_i) – главный член погрешности, и - приближенные решения в точке x_i, найденные с шагом h и 2h соответственно.

Пример 6.1. Решить дифференциальное уравнение на отрезке [0, 1] c начальным условием y(x=0) = 1. Найти первые три точки, приняв шаг h = 0.05.

Решение. Поставленная задача была решена методом разложения в ряд Тейлора (6.3); методом Эйлера (6.6) и методом Рунге-Кутта (6.12). Для наглядности все полученные результаты сведем в табл. 6.1.

 

Таблица 6.1

xi	Ряд Тейлора (m=1)	Метод Эйлера	Метод Рунге-Кутта
yi	yi	yi	f(xi, yi)	φ 0	φ 1	φ 2	φ 3
					-	-	-	-
0.05	1.05	1.05	1.0477	0.9089	0.05	0.0477	0.0476	0.0454
0.1	1.1	1.0931	1.0912	0.8321	0.0454	0.0435	0.0434	0.0416
0.15	1.15	1.1347	1.1311	0.7658	0.0416	0.0399	0.0399	0.0383

 

 

Многошаговые методы

 

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

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

Будем, как и раньше рассматривать задачу Коши:

 

(6.14)

Ограничимся рассмотрением многошаговых методов с равномерной сеткой:

x_i = x₀ + ih; i = 0, 1,..., n; n·h = b - x₀.(6.15)

 

Рассмотрим вычислительные правила вида

 

(6.16)

 

Среди вычислительных правил вида (6.16) особенно широко известны экстраполяционные (при s = 0) и интерполяционные (при s = 1, A_-1 ¹ 0).

 

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: