УМК (1013374), страница 24
Текст из файла (страница 24)
В отличие от метода Рунге–Кутты четвертого порядка в этих методах требуется вычислятьтолько одно новое значение правой части решаемого уравнения (системы) вместо четы-141рех. Высокая точность методов достигается при этом за счет учета информации о предыдущих точках. Напротив, в методе Рунге–Кутты, как и в других одношаговых методах,недостающую информацию о поведении правых частей системы получают в результатевычислений в специальным образом выбранных дополнительных точках.А6. Явные методы ХеммингаМногошаговый метод Хемминга четвертого порядка точности может быть реализован тремя различными способами, в каждом из которых для нахождения точки yˆ i + 1используются четыре предыдущие точки:yˆ i +1 =илиyˆ i +1 =илиyˆ i +1 =yˆ i + yˆ i −122 yˆ i −1 + yˆ i −23++h[191 f i − 107 f i −1 + 109 f i − 2 − 25 f i −3 ] , i = 3, n − 1 ;72yˆ i + yˆ i −1 + yˆ i − 23h[119 f i − 99 f i −1 + 69 f i −2 − 17 f i −3 ] , i = 3, n − 1 ;48+h[ 91 f i − 63 f i −1 + 57 f i −2 − 13 f i −3 ] , i = 3, n − 1 ;36где f i = f ( x i , yˆ i ) .
Для начала расчетов по любой из приведенных формул требуетсячетыре «разгонные» точки yˆ0 , yˆ1 , yˆ2 , yˆ3 .А7. Методы прогноза и коррекцииРассматриваемые здесь методы (схемы), называемые составными, известны подобщим названием методов прогноза и коррекции. Из названия следует, что сначала«предсказывается» значение ŷi +1 , а затем используется тот или иной метод для «корректировки» этого значения.Таким образом, составные схемы включают в себя два шага (этапа) расчета очередного значения ŷi +1 :1.
Шаг «предиктор» (предсказание), на котором рассчитывается предсказанное(предварительное) значение yˆi(+П1) .2. Шаг «корректор» (коррекция), на котором предсказанное значение уточняется.В результате находится значение yˆi(+К)1 , которое принимается за ŷi +1 . Если промежутокинтегрирования не исчерпан, оно далее используется при реализации очередного шага«предиктор» для нахождения следующего предсказанного значения yˆi(+П2) .Первый шаг реализуется с помощью явных методов, а второй шаг основан на применении формул неявных методов, в правую часть которых вместо неизвестного значения ŷi +1 подставляется результат предсказания.
Схемы такого типа называются такжесхемами «предиктор-корректор» и в итоге относятся к явным методам.142Приведем наиболее часто встречающиеся составные схемы.• Предсказание с помощью явного метода Эйлера или метода Эйлера–Коши, коррекция по методу трапеций.Шаг «предиктор»:yˆi(+П1) = yˆi + hi +1 f ( x i , yˆi ) ,или при условии hi +1 = h = constyˆi(+П1) = yˆi −1 + 2h ⋅ f ( x i , yˆi ),где ŷ i и ŷi −1 рассчитаны на предыдущих шагах.Шаг «корректор»:)ˆi +yˆ i +1 ≡ yˆ i(К+1 = yhi +12[ f ( x i , yˆ i ) + f ( x i + hi +1 , yˆ i(П)+1 )] .• Предсказание по методу Адамса–Бэшфорта третьего или четвертого порядка,коррекция по методу Адамса–Мултона четвертого порядка (см.
неявные методы)(при hi +1 = h = const ).Шаг «предиктор»:hyˆi(+П1) = yˆi + [23 f i − 16 f i −1 + 5 f i − 2 ] ,12илиhyˆi(+П1) = yˆi +[55 f i − 59 f i −1 + 37 f i − 2 − 9 f i − 3 ] .24Шаг «корректор»:hyˆi +1 ≡ yˆi(+К1) = yˆi +[ f i − 2 − 5 f i −1 + 19 f i + 9 f ( x i +1 , yˆi(+П1) )] .24• Метод Хемминга четвертого порядка (при hi +1 = h = const ).Шаг «предиктор»:4hyˆi(+П1) = yˆi − 3 +[2 f i − f i −1 + 2 f i − 2 ] .3Шаг «корректор»:13hyˆi +1 ≡ yˆi(+К1) = (9 yˆi − yˆi − 2 ) +[− f i −1 + 2 f i + f ( x i +1 , yˆi(+П1) )] .88З а м е ч а н и е. Среди явных нашли также широкое применение методы Фельберга, Ингленда, Нюстрема, Милна, интерполяционные методы [3].143Лекция 17Б. НЕЯВНЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ОБЫКНОВЕННЫХДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙБ1. Неявный метод ЭйлераФормула неявного метода Эйлера первого порядка точности:yˆi +1 = yˆi + hi +1 f ( x i +1 , yˆi +1 ) ≡ Φ( x i , x i +1 , yˆi +1 ) , i = 0, n − 1 .Подчеркнем, что свойство неявности схемы обусловлено наличием искомойвеличины ŷi +1 в левой и правой частях в общем случае нелинейного уравнения.
Можнопоказать, что неявный метод Эйлера обладает свойством А-устойчивости. Приреализации алгоритма решения задачи Коши неизвестное значение ŷi +1 вычисляетсяодним из методов решения нелинейных уравнений. Применение метода Ньютона связанос записью уравнения в формеyˆi +1 − Φ( x i , x i +1 , yˆi +1 ) ≡ F ( yˆi +1 ) = 0и с дифференцированием функции F ( yˆi +1 ) , что увеличивает время расчетов из-завозможной сложности вычисления производных.Как правило, используется метод простых итераций:yˆi(+k1+1) = Φ( x i , x i +1 , yˆi(+k1) ) , k = 0,1,....При применении методов Ньютона и простых итераций вначале задается илинаходится нулевое приближение решения по формуле yi(+01) = yˆi (так называемый«постоянный» прогноз) или явным методом Эйлера:yˆi(+01) = yˆi + hi +1 f ( x i , yˆi ) .Итерации завершаются при выполнении условия окончанияyˆ i(+k1+1) − yˆ i(+k1) ≤ ε ,где ε – малое положительное число.Б2.
Метод трапецийФормула метода трапеций - неявная одношаговая схема второго порядкаточности:yˆi +1 = yˆi +hi +12[ f i + f (xi +1 , yˆi +1 )] ≡ Φ(xi , xi +1 , yˆi +1 ) , i = 0, n − 1 ,144где f i = f ( x i , yˆi ) . Подчеркнем, что свойство неявности схемы обусловлено наличиемискомой величины ŷi +1 в левой и правой частях в общем случае нелинейного уравнения.Неизвестное значениеŷi +1 вычисляется одним из методов решения нелинейныхуравнений.
Можно показать, что метод трапеций является А-устойчивым.Б3. Методы Адамса–МултонаМногошаговые неявные схемы Адамса–Мултона:– первого порядка (неявный метод Эйлера);– второго порядка (метод трапеций);– третьего порядка:hyˆi +1 = yˆi + [− f i −1 + 8 f i + 5 f ( x i +1 , yˆi +1 )] ,12i = 1, n − 1 ;– четвертого порядка:hyˆi +1 = yˆi +[ f i − 2 − 5 f i −1 + 19 f i + 9 f ( x i +1 , yˆi +1 )] , i = 2, n − 1 ;24иhyˆ i +1 = yˆ i −1 + [ f i −1 + 4 f i + f ( x i +1 , yˆ i +1 )] , i = 1, n − 1 (неявная схема парабол);3– пятого порядка:yˆ i +1 = yˆ i +h[−19 f i −3 + 106 f i − 2 − 264 f i −1 + 646 f i + 251 f ( x i +1 , yˆ i +1 )] , i = 3, n − 1 .720где f i = f ( x i , yˆ i ), f i −1 = f ( x i −1 , yˆ i −1 ), f i −2 = f ( x i −2 , yˆ i −2 ), f i −3 = f ( x i −3 , yˆ i −3 ) .Для расчетов по формулам требуется получить соответствующее число«разгонных» точек.
Чтобы найти искомое значение ŷi +1 , так же как в неявном методеЭйлера и методе трапеций, требуется решить в общем случае нелинейное уравнение.З а м е ч а н и е. Среди неявных также получили распространение методы Гира,Милна, Хемминга, Рунге–Кутты [3].145ПРАКТИЧЕСКИЕ ЗАНЯТИЯЗанятие 1.
НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯБЕЗУСЛОВНОГО ЭКСТРЕМУМАПостановка задачиДана дважды непрерывно дифференцируемая функция f ( x) , определенная намножестве X = R n .Требуется исследовать функцию f ( x) на экстремум, т.е. определить точки x ∗ ∈ R nее локальных минимумов и максимумов на R n :f ( x∗ ) = min f ( x) ;f ( x∗ ) = max f ( x) .x∈R nx∈R nСхема исследования функций на безусловный экстремумНеобходимые условия экстремумапервого порядкаДостаточные условияэкстремумаВычислить значения функциив точках экстремумаНет экстремумаНеобходимые условия экстремумавторого порядкаПродолжениеисследованийНет экстремумаНеобходимые условия экстремума первого порядка.
Пусть x ∗ ∈ R n есть точкалокального минимума (максимума) функции f ( x) на множестве R n и f ( x) дифференцируема в точке x ∗ . Тогда все частные производные функции f ( x) первого порядка вточке x ∗ равны нулю, т.е.∂ f ( x∗ )= 0,∂ xi146i = 1,..., n .Точки x ∗ , удовлетворяющие необходимому условию, называются стационарными.Рассмотрим определитель матрицы Гессе H ( x∗ ) , вычисленной в стационарнойh11 h12h1nhhh2n.точке x * : det H ( x∗ ) = 21 22hn1hn 2hnn1. Определители Δ1 = h11 ,hΔ 2 = 11h21h12,..., Δ n =h22h11h1nназываютсяhn1hnnугловыми минорами.2.
Определители m -го порядка ( m ≤ n ), получающиеся из определителя матрицыH ( x∗ ) вычеркиванием каких-либо ( n − m ) строк и ( n − m ) столбцов с одними и темиже номерами, называются главными минорами.Первый способ проверки достаточных и необходимых условий второго порядка.Критерий проверки достаточных условий экстремума (критерий Сильвестра).Если знаки угловых миноров строго положительны:Δ1 > 0 , Δ 2 > 0 ,..., Δ n > 0 ,то точка x ∗ является точкой локального минимума.Если знаки угловых миноров чередуются, начиная с отрицательного:Δ1 < 0 , Δ 2 > 0 , Δ 3 < 0 ,...,( −1) n Δ n> 0,то точка x ∗ является точкой локального максимума.Критерий проверки необходимых условий экстремума второго порядка1.
Для того чтобы матрица Гессе H ( x∗ ) была положительно полуопределенной( H ( x∗ ) ≥ 0 ) и точка x ∗ может быть являлась точкой локального минимума, необходимо и достаточно, чтобы все главные миноры определителя матрицы Гессе были неотрицательны.2. Для того чтобы матрица Гессе H ( x∗ ) была отрицательно полуопределенной( H ( x∗ ) ≤ 0 ) и точка x ∗ может быть являлась точкой локального максимума, необходимо и достаточно, чтобы все главные миноры четного порядка были неотрицательны,а все главные миноры нечетного порядка – неположительны.Второй способ проверки достаточных и необходимых условий второго порядка(с помощью собственных значений матрицы Гессе).Собственные значения λ i , i = 1,..., n , матрицы H ( x∗ ) размеров ( n × n ) находятсякак корни характеристического уравнения (алгебраического уравнения n -й степени):147H ( x∗ ) − λE =h11 − λh12h1nh21h22 − λh2nhn1hn 2= 0.… hnn − λТаблица1п/п1Второй способТип стационарной точки x ∗λ1 > 0,..., λ n > 0Локальный минимум2λ1 < 0,..., λ n < 0Локальный максимум3λ1 ≥ 0,..., λ n ≥ 04λ1 ≤ 0,..., λ n ≤ 05λ1 = 0,..., λ n = 06λ i имеют разныезнакиМожет быть локальный минимум,требуется дополнительное исследованиеМожет быть локальный максимум,требуется дополнительное исследованиеТребуется дополнительное исследованиеНет экстремумаПример 1.
Найти экстремум функции f ( x ) = − x12 − x 22 − x 32 − x1 + x1 x 2 + 2 x3 намножестве R 3 . 1. Запишем необходимые условия экстремума первого порядка:∂ f ( x)= −2 x1 − 1 + x2 = 0 ,∂ x1∂ f ( x)= −2 x2 + x1 = 0 ,∂ x2∂ f ( x)= −2 x3 + 2 = 0 .∂ x3T1 ⎞⎛ 2В результате решения системы получим стационарную точку x = ⎜ − , − , 1⎟ .3 ⎠⎝ 3∗2. Проверим выполнение достаточных условий экстремума.148( )Первый способ. Матрица Гессе имеет вид H xΔ1 = −2 < 0 , Δ 2 =∗⎛ −2 1 0 ⎞⎜⎟= ⎜ 1 −2 0 ⎟ . Так как⎜ 0 0 −2 ⎟⎝⎠−2 1= 4 − 1 = 3 > 0 , Δ 3 = ( −2 ) ⋅ 3 = −6 < 0 , т.е. знаки угловых миноров1 −2чередуются, начиная с отрицательного, то точка x ∗ – точка локального максимума.Второй способ.