Настоящие корни уравнения 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) имеет противоположные символы. Новый суженный отрезок [a1, b1] опять делим пополам и проводим тот же анализ и т.д.
Разумеется, что закончить уточнение значения корня возможно при достижении условия |аj – bj| ? , где ? 0 — сколь угодно малое число. Второй метод закончить вычисления — задать большое значение невязки:
f((aj + bj)/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). Наряду с этим новое значение корня определяется из соотношения
x1 = a + h1, (4.5)
где
. (4.6)
Потом данный прием используем к одному из отрезков[a, x1] либо [x1, b], на финишах которого функция f(x) имеет противоположные символы. Подобно находим второе приближение x2 и т.д. (см. рис. 4.2.).
Геометрически данный метод эквивалентен замене кривойy = f(x) хордой, проходящей через точкиА(a, f(a)) и B(b, f(b)).
Рис. 4.2. Уточнение корня уравнения способом хорд
Вправду, уравнение хорды АВ имеет форму
(4.7)
Учитывая, что при х = х1 = 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-ое приближение корня , мы можем уточнить его по способу Ньютона следующим образом. Пускай
? = xn + hn, (4.14)
где hn — величина малая. Из этого по формуле Тейлора возьмём (ограничиваясь первым порядком малости довольно hn)
f(xn + hn) = f(xn) + hn f¢(xn) = 0. (4.15)
Следовательно,
hn = — f(xn) / f¢ (xn). (4.16)
Подставив полученное выражение в формулу (4.14), отыщем следующее (по порядку) значение корня:
(4.17)
Проиллюстрируем графически нахождение корня способом Ньютона (рис. 4.3.).
Рис. 4.3. Уточнение корня способом касательных
В случае, если вкачестве начального приближения выбрать точкух0 = В0 , то процесс скоро сходится. В случае, если же выбрать точку х0 = А0, то х1 [a, b],и процесс нахождения корня расходится. Рекомендуется: в качествех0 выбрать точку, где 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) = x5 – 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) воспользуемся способом последовательных приближений. Предположим, что отыскано р-ое приближение xp = (x1(p), x2(p) , …, xn(p))одного из изолированных корней x = (x1, x2, x3, …, xn) векторного уравнения (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) направляться осознавать матрицу Якоби совокупности функций f1 , f2, …, fn, довольно переменных x1, x2, x3, …, xn, другими словами:
. (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(0) возможно забрать приближенное (неотёсанное) значение искомого корня.
Пример 5.1.Разглядим использование способа Ньютона на примере совокупности двух нелинейных уравнений
(5.12)
Перед тем как разбирать конкретные шаги согласно решению совокупности (5.12), распишем в общем виде якобиан для совокупности из двух уравнений
Тут A, B, C, D – функционалы от переменных x1, x2. Нас практически интересует W-1. Пускай матрица W- неособенная, тогда обратная матрица вычисляется
Сейчас возвратимся к совокупности (5.12). Графическое ответ данной совокупности дает две точки пересечения: М1 (1.4; -1.5) и М2 (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. Ответ обычных
дифференциальных уравнений
Способы ответа задачи Коши
Среди задач, с которыми приходится иметь дело в вычислительной практике, большую часть составляют разные задачи, сводящиеся к ответу обычных дифференциальных уравнений. В большинстве случаев приходится прибегать к помощи приближенных способов ответа аналогичных задач. При обычных дифференциальных уравнений в зависимости от того, ставятся ли дополнительные условия в одной либо нескольких точках отрезка трансформации свободной переменной, задачи в большинстве случаев подразделяются на одноточечные (задачи с начальными условиями либо задачи Коши) и многоточечные. Среди многоточечных задач чаще всего в прикладных вопросах видятся так именуемые граничные задачи, в то время, когда дополнительные условия ставятся на финишах разглядываемого отрезка.
В будущем ограничимся рассмотрением численных способов ответа задачи Коши. Для простоты изложения способов ответа задачи будем разглядывать случай одного обычного дифференциального уравнения первого порядка.
Пускай на отрезке x0 ? x ? b требуется отыскать ответ y(x) дифференциального уравнения
, (6.1)
удовлетворяющее при x = x0 начальному условию
(6.2)
Будем вычислять, что единственности решения и условия существования поставленной задачи Коши выполнены.
На практике отыскать общее или частное ответ задачи Коши удается очень редко, исходя из этого приходится решать эту задачу приближенно. Отрезок [x0, b] накрывается сеткой (разбивается на промежутки) значительно чаще с постоянным шагом h ( h = xn+1 — xn ), и по какому-то важному правилу находится значение yn+1 = y(xn+1). Так, в качестве ответа задачи Коши численными способами мы приобретаем таблицу, складывающуюся из двух векторов:
x = (x0 , x1 , …xn) –вектора доводов и соответствующего ему вектора функции y = ( y0 , y1,… yn ).
Численные способы (правила), в которых для нахождения значения функции в новой точке употребляется информация лишь об одной (прошлой) точке, именуются одношаговыми.
Численные способы (правила), в которых для нахождения значения функции в новой точке употребляется информация о нескольких (прошлых) точках, именуются многошаговыми.
Из неспециализированного курса обычных дифференциальных уравнений широкое распространение взял аналитический способ, основанный на идее разложения в ряд ответа разглядываемой задачи Коши. Особенно довольно часто для этих целей употребляется последовательность Тейлора. В этом случае вычислительные правила строятся особенно легко. Наряду с этим приближенное ответ ym(x) исходной задачи ищут в виде
(6.3)
Тут а значения i = 2, 3,…m находят по формулам, взятым последовательным дифференцированием уравнения (6.1):
(6.4)
Для значений x, родных к x0, способ последовательностей (6.3) при большом значении m дает в большинстве случаев хорошее приближение к правильному ответу y(x) задачи (6.1). Но с ростом расстояния ex — x0e погрешность приближенного равенства y(x) » ym(x), по большому счету говоря, возрастает по безотносительной величине, и правило (6.3) делается вовсе неприемлемым, в то время, когда x выходит из области сходимости соответствующего последовательности (6.3) Тейлора.
В случае, если в выражении (6.3) ограничиться m = 1, то для вычисления новых значений y(x) нет необходимости пересчитывать значение производной, правда и точность ответа будет низка. Графическая интерпретация этого способа приведена на рис. 6.1.
Рис. 6.1. Разложение функции в ряд Тейлора (m=1)
6.2. Способ последовательностей, не требующий вычисления производных
правой части уравнения
Конечно поставить задачу о таком усовершенствовании вышеприведенного одношагового способа, которое сохраняло бы главные его преимущества, но не было бы связано с нахождением значений производных правой части уравнения
(6.5)
где xn+1 = xn + h.
Дабы выполнить это условие (последнее), производные y(i)(x),
i = 2, 3,…, m, входящие в правую часть уравнения (6.5), возможно заменить по формулам численного дифференцирования их приближенными выражениями через значение функции y’ и учесть, что y'(x) = f [x, y(x)].
При m = 1 приближенное равенство (6.5) не требует вычисления производных правой части уравнения и разрешает с погрешностью порядка h2 обнаружить значение y(xn+ h) решения этого уравнения по известному его значению y(xn). Соответствующее одношаговое правило возможно записать в виде
(6.6)
Это правило (6.6) в первый раз было выстроено Эйлером и носит его имя. Время от времени его именуют кроме этого правилом ломаных либо способом касательных. Способ Эйлера имеет несложную геометрическую интерпретацию (см. рис. 6.2).
Рис. 6.2. Нахождение ответа способом Эйлера
ЗамечаниеМетод Эйлера имеет порядок точности ~ h2 на одном шаге. Практическая оценка погрешности приближенного ответа возможно взята по правилу Рунге.
Способ Рунге-Кутта
Изложим идею способа на примере задачи Коши:
(6.7)
Интегрируя это уравнение в пределах от x до x + h (0 h
(6.8)
которое при помощи последнего интеграла связывает значения ответа разглядываемого уравнения в двух точках, удаленных друг от друга на расстояние шага h.
Для удобства записи выражения (6.8) используем обозначение
?y = y(x + h) – y(x) и замену переменной интегрирования t = x + ah. Совсем возьмём:
(6.9)
Указав действенный способ приближенного вычисления интеграла в выражении (6.9), мы возьмём наряду с этим одно из правил численного интегрирования уравнения (6.7).
Попытаемся составить линейную комбинацию размеров ji,
i = 0, 1, …, q, которая будет являться аналогом квадратурной суммы и разрешит вычислить приближенное значение приращения Dy:
(6.10)
где
Способ четвертого порядка для q = 3, являющийся аналогом широко известной в литературе четырехточечной квадратурной формулы трех восьмых, имеет форму
(6.11)
где
Очень обширно известно второе вычислительное правило типа Рунге-Кутта четвертого порядка точности:
(6.12)
где
Способ Рунге-Кутта имеет погрешность четвертого порядка (~ h4 ).
Правило Рунге. В случае, если приближенный способ имеет порядок погрешности m, то погрешность возможно приближенно оценить по формуле
(6.13)
В формуле (6.13) O(xi) – основной член погрешности, и — приближенные ответы в точке xi, отысканные с шагом 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)
Ограничимся рассмотрением многошаговых способов с равномерной сеткой:
xi = x0 + ih; i = 0, 1,…, n; n·h = b — x0. (6.15)
Разглядим вычислительные правила вида
(6.16)
Среди вычислительных правил вида (6.16) особенно легендарны экстраполяционные (при s = 0) и интерполяционные (при s = 1, A-1 ¹ 0).