Вычислительная математика лекции. Конспект лекций. Санкт петербург 2011 2 Оглавление
 Скачать 3.86 Mb.
|
|
Теорема1. Предположим, что матрица A строго диагонально доминирующая, т. е. 1 | | | |, i=1, . n ii ij j a a n Тогда итерации Якоби и Гаусса – Зейделя сходятся к единственному решению уравнения Ax=b при любом начальном приближении x (0) Теорема 2. Если A симметрическая и положительно определенная матрица, то при любом начальном приближении x (0) итерации Гаусса – Зейделя сходятся к единственному решению уравнения Ax=b Обычно скорость сходимости выше у метода Зейделя. Однако встречаются системы, для которых нарушается сходимость метода Зейделя , а метод Якоби функционирует нормально. Бывает и наоборот. Обобщение матричных форм методов Якоби и Зейделя приводит к канонической форме одношагового итерационного метода 1 1 1 n n n n n x x B Ax b Известны многочисленные модификации итерационных методов. Например, в качестве вариантов канонической формы можно перечислить 1. Метод простой итерации: B n+1 =E, τ n+1 =τ. 146 2. Итерационный метод Ричардсона: B n+1 =E, τ n+1 переменный параметр. 3. Метод Якоби: B n+1 =D, τ n+1 =1. 4. Метод верхней релаксации: B n+1 =D+ωA 1 , τ n+1 =ω, 0<ω<2. Для ω=1 получаем метод Зейделя. Итерационные методы используются для решения систем с большими разреженными матрицами. В этих условиях критичной становится скорость сходимости. Существенно повысить скорость сходимости можно, подбирая оптимальные значения τ n+1 и B n+1 11.7. Решение линейных алгебраических систем с трехдиагональной матрицей методом прогонки. Требуется решать линейную систему Ax = r , (1) где x=(x 0 , x 1 , ….,x N ) T , r = (r 0 , r 1 , ….,r N ) T , 0 0 1 1 1 2 2 2 1 1 1 N N N N N c d b c d b c d A b c d b c Нулевое соотношение системы (1) с 0 x 0 + d 0 x 1 = r 0 решаем относительно x 0 : 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 или x , где , d r d r x x x c c c c Следующее уравнение b 1 x 0 + с 1 x 1 + d 1 x 2 = r 1 , используя выражение для x 0 , преобразуем следующим образом: b 1 δ 0 x 1 +b 1 λ 0 + с 1 x 1 + d 1 x 2 = r 1 или (b 1 δ 0 + с 1 )x 1 = - d 1 x 2 +( r 1 -b 1 λ 0 ), получим x 1 = δ 1 x 2 +λ 1 , где 147 1 1 1 0 1 1 1 0 1 1 0 1 , d r b b c b c Рассмотрим k – ое соотношение b k x k-1 + с k x k + d k x k+1 = r k , предполагая, что на предыдущем k-1 – ом шаге было получено x k-1 = δ k-1 x k +λ k-1 . Получим b k δ k-1 x k +b k λ k-1 + с k x k + d k x k+1 = r k , или x k = δ k x k+1 +λ k , (2) где 1 1 1 , k k k k k k k k k k k k d r b b c b c (3) Из соотношений (3) можно найти все коэффициенты δ k , λ k для 1, 1, k N преобразуя систему (1) к соотношениям вида (2). Из последнего уравнения (1) b N x N-1 + c N x N = r N после подстановки x N-1 = δ N-1 x N +λ N-1 получим 1 1 N N N N N N N r b x b c Затем по соотношению (2) в обратном порядке находят остальные неизвестные x N-1 , x N-2 , …, x 1 , x 0 Процесс вычисления коэффициентов δ k , λ k для 1, 1, k N по соотношениям (3) называется прямым ходом прогонки, а нахождение неизвестных по формуле (2) – обратным ходом прогонки. Если выполняется условие |c k | ≥|b k | + |d k |, то говорят, что матрица А является матрицей с доминирующей главной диагональю. Указанное условие гарантирует корректность и вычислительную устойчивость алгоритма. При этом знаменатель δ k в (3)не равен нулю, что обеспечивает выполнение прямого хода. Дополнительное условие |c k | ≥|b k | обеспечивает δ k 1, что делает вычислительно устойчивым обратный ход. Являясь модификацией метода Гаусса, метод прогонки существенно более экономен и требует для своей реализации всего 8(N+1) операций. 148 12. Методы отыскания решений нелинейных уравнений. 12. 1. Постановка задачи. Требуется вычислить корни системы из n уравнений с n неизвестными 1 1 2 2 1 2 1 2 ( , ,..., ) 0 ( , ,..., ) 0 ( , ,..., ) 0 n n n n f x x x f x x x f x x x Матричная запись F(x)=0, x=(x 1 , x 2 ,…,x n ) T , F=(f 1 , f 2 ,…,f n ) T Ограничимся отысканием вещественных корней. На первом этапе займемся отысканием решения одного нелинейного уравнения. Ограничимся вещественными корнями. Корень x простой, если f'( x ) ≠0, корень x имеет кратность m, если f (k) ( x ) = 0, k=1, 2, …, m-1 и f (m) ( x ) ≠0. x3 x1 x2 x4 x5 x1, x2, x4 – простые корни; x3 – корень четной степени; x5 кратный корень нечетной степени 12. 2. Основные этапы решения. Локализация корня. 149 Корень локализован на отрезке [a,b], если f(a)f(b)<0 и f'(x) знакопостоянна на этом отрезке. К сожалению, кратный корень не может быть локализован таким образом. Можно использовать построение графиков и таблиц. Особенно трудна задача локализации при решении систем уравнений. Часто в этом случае приходится использовать метод проб и ошибок. Итерационное уточнение корня. Используются итерационные численные методы. Задается закон формирования числовой последовательности x n+1 =g(x n , x n-1 ,…) такой, что x n → x при n →∞. Выполнение последнего условия означает сходимость метода, что является необходимым условием его работоспособности. Метод называется одношаговым, если список аргументов функции g содержит только один предшествующий член последовательности. Если в этом списке присутствуют несколько предыдущих членов, метод называется многошаговым. Если существует такая ϭ окрестность корня, что когда x ϭ, выполняется условие |x n+1 - x | C|x n - x | p , C>0 , p ≥1, говорят о p-ом порядке скорости сходимости метода. Линейной скорости соответствует p=1. Если при этом C=q<1, метод сходится со скоростью геометрической прогрессии. Метод обладает сверхлинейной сходимостью при p>1. В этом случае скорость сходимости возрастает по мере уменьшения погрешности |x n - x |. Сказанное справедливо для системы, если использовать нормы векторов вместо абсолютного значения. 12. 3. Обусловленность задачи вычисления корня. Пусть функция f(x) в окрестности корня вычисляется с погрешностью |f(x)-f*(x)| Δ(f).Здесь f*(x) возмущенная функция. Тогда за 150 решение x можно принять любое значение x*, которое является точным решением любой функции f*(x), обладающей свойством |f( x )-f*(x)| Δ(f) или |f*(x)| Δ(f) . 2ρ 2 Δ(f) f(x) Разлагаем f(x) в окрестности x в ряд Тэйлора f(x)-f( x )=f'(ξ)(x- x ), т. е. f(x)=f'(ξ)(x- x ), x- x =f(x)/f'(ξ), |(x- x )| f(x)| / |f'(ξ)|. Значение функции f(x) уменьшается при приближении x к корню. Когда оказывается |f(x)| Δ(f) , дальнейшее уточнение корня становится невозможным. Таким образом, радиус неопределенности корня ρ Δ(f) / |f'( x )| . Практические выводы. 1. Непосредственный расчет ρ по последней формуле невозможен. Однако так как при попадании в область неопределенности погрешность очередных уточнений перестает уменьшаться, можно воспользоваться правилом Гарвика 1 1 2 | | 1 | | n n n n n x x q x x . При выполнении этого условия расчет нужно прекратить. Это правило легко распространяется на систему при замене абсолютных значений на нормы. 2. Точность вычисления корня заведомо не может быть выше ε маш 151 12. 4. Методы отыскания решений нелинейных уравнений. 12. 4.1 Метод бисекции. Описание метода. Пусть вычислен исходный отрезок локализации [a 0 , b 0 ], задана погрешность ε.Последовательность действий задается следующим алгоритмом. 1.Вводят исходные данные: f(x), a=a 0 , b 0 =b, ε. 2. Рассчитывают x=(b-a)/2. 3. Если b-a 2ε, получен результат. Вывод x. 4. Если f(a)f(x) 0, то b=x. В противном случае a=x.Возврат к пункту 2. Графическая иллюстрация представлена на рисунке. 2 Δ(f) a 0 b 0 x 0 x 1 Скорость сходимости. Середина n-ого отрезка дает приближение к корню x с оценкой погрешности |x n - x | 0 0 1 2 2 n n n b a b a Таким образом, метод сходится со скоростью геометрической погрешности, знаменатель которой равен q=1/2. Влияние вычислительной погрешности. 152 В процессе вычислений важно правильно определять знак функции. Если очередное приближение попадает в интервал неопределенности, нет гарантии правильности знака. Метод очень надежен. Гарантирует точность, равную радиусу неопределенности. 12. 4.2 Метод простых итераций. Описание метода. Задача f(x)=0 преобразуется к виду x=φ(x). Итерационный процесс строится по закону x n+1 =φ(x n ), n=0,1,… . При удачном выборе φ(x) x n → x , если n →∞. Графическая интерпретация. Корень уравнения x=φ(x) есть точка пересечения графиков y=x и y=φ(x) 153 a), c) процесс сходится при любом начальном приближении x 0 , |φ'(x)|<1. b), d) процесс расходится при любом начальном приближении x 0 , |φ'(x)|>1. Сходимость. Так как x =φ( x ), то x n+1 - x = φ(x n ) – φ( x )=φ'(ξ n )(x n - x ). |x n+1 - x | |φ'(ξ n )| |(x n - x )|. Таким образом, условие линейной сходимости |φ'( x )| =q<1 ( '( ) '( )) x Критерий окончания. 154 x n - x ≈φ'( x )(x n-1 - x )=φ'( x )[(x n - x )+(x n-1 -x n )]. Следовательно, x n - x ≈[φ'( x )/(1-φ'( x ))](x n-1 -x n ) и |x n - x | [q/(1-q)]|x n-1 -x n |. Критерий останова по заданной погрешности имеет вид |x n-1 -x n | ε(1-q)/q. Замечания. 1. Часто используют критерий останова |x n-1 -x n |<ε. Это оправдано, если q 1/2. В случае ½ -x n |=|φ(x n-1 ) – φ(x n-2 )| q|x n-1 -x n-2 |, q ≥|x n-1 -x n |/|x n-1 -x n-2 |. Приведение уравнения к виду, удобному для итераций Основным критерием является условие q<1.Иногда исходная функция разрешима относительно x. В самом общем случае возможна запись x=x-w(x)f(x), w(x) ≠0 x [a,b]. Простейшим вариантом является: x=x-αf(x). 12.4.3 Метод Ньютона. Основной метод. Обладает квадратичной сходимостью, однако требует достаточно точного начального приближения. Для отыскания начального приближения иногда приходится использовать менее точные вспомогательные методы (например, метод бисекции). Описание метода. Это итерационный метод, очередной член итерационной последовательности которого находится решением линейного уравнения, полученного в результате линеаризации функции f(x). Пусть имеется найденное приближение x k . Пытаемся найти малую добавку Δx такую, чтобы x k +Δx= x . Для её определения запишем 155 уравнение f(x k +Δx)=0. Используя предположение о малости Δx, его можно линеаризовать, разложив функцию в ряд Тэйлора по Δx. f(x k +Δx )=f(x k )+f'(x k )Δx + 1 ''( ) 2 f (Δx) 2 =0. f(x k )+f'(x k )( x -x k ) + 1 ''( ) 2 f ( x -x k ) 2 =0 (*) Пренебрегая б. м. высших порядков по Δx, имеем линейное уравнение, решением которого в силу его приближенности является не Δx, но очередное приближение Δx k+1 =x k+1 -x k к x f(x k )+f'(x k )Δx k+1 =0 f(x k )+f'(x k )(x k+1 -x k )=0 (**) Вычислительный алгоритм в первом приближении имеет вид. 1.Задаемся начальным приближением x 0 2. Вычисляем f(x 0 ) и f'(x 0 ). 3.Решаем линейное уравнение f(x 0 )+f'(x 0 )Δx=0. 4.Находим уточненное приближение x= x 0 +Δx 5. Проверяем критерий окончания вычислений |x-x 0 | ε зад 6. Если критерий выполнен, x найденное решение. Иначе x 0 =x и переход к п.2. Требуется уточнить несколько моментов. 1. Как выбирать x 0 2. Требует доказательства справедливость критерия останова. 3.Должна быть установлена сходимость метода. Сходимость метода. Теорема. Пусть x простой корень уравнения . Предположим, что в некоторой ϭ - окрестности x : |x- x |<ϭ выполнены следующие условия: 1.f(x) гладкая функция в смысле существования её непрерывных производных до второго порядка включительно. 156 2. Имеют место оценки |f'(x)| c 1 ; |f''(x)| c 2 . Отметим, что c 1 ≠0, так как x простой корень. Тогда, если начальное приближение x 0 достаточно близко к x , метод сходится и имеет место квадратичная скорость сходимости. Замечание. Выражения "некоторая окрестность", "x 0 достаточно близко к x " поясняются в ходе доказательства. Доказательство. Вычитая (**) из (*), получаем f'(x k )(x k+1 - x ) = 1 ''( ) 2 f ( x -x k ) 2 (x k+1 - x ) =[ 1 ''( ) 2 f /f'(x k )]( x -x k ) 2 Таким образом, |x k+1 - x | C|x k - x | 2 , C= 2 1 2 c c Здесь учтены оценки производных в п.2 формулировки теоремы. Имеем цепочку |x 1 - x | C|x 0 - x | 2 , |x 2 - x | C|x 1 - x | 2 1 C (C|x 0 - x |) 4 …и т. д. |x k - x | 1 C 2 0 (C | x |) k x Для сходимости необходимо, чтобы |x k - x | →0 при k→∞. Для этого должно выполняться C|x 0 - x |=q<1. Отсюда следует требование к области ϭ выбора начального приближения |x 0 - x |<1/C, то есть σ=1/C. Выражение |x k+1 - x | C|x k - x | 2 доказывает квадратичную сходимость метода. Если ϥ<1, то |x k - x | 1 C 2 0 (C | x |) k x = 1 C 2 k q < 1 C q=|x 0 - x |(***), то есть x k не выходит за пределы ϭ. Пусть условия п.2 теоремы выполняются, когда |x 0 - x |<δ. Предыдущие рассуждения справедливы, если δ 1 C , то есть δ - область шире ϭ - области. 157 В противном случае область выбора x 0 следует ограничить: |x 0 - x | δ. При этом условие ϥ<1 будет усилено и продолжит выполняться неравенство (***). Теперь x k не выходит за пределы δ. Критерий останова. Теорема. Пусть выполнены условия предыдущей теоремы и |x 0 - x |<ϭ/2. Тогда для всех k 1 верна оценка |x k - x | |x k -x k-1 |. Доказательство. Отметим, что мы заведомо сузили область задания начального приближения. Неравенство (***) продолжает выполняться, т.е. |x k - x | <|x 0 - x |<ϭ/2= 1 2C Из цепочки неравенств: 2|x k+1 - x | 2C|x k - x | 2 |x k - x | |x k -x k+1 |+|x k+1 - x | следует оценка, заявленная в условиях теоремы. Модификации метода Ньютона. Усовершенствования направлены на решение двух основных проблем: 1.Критичность выбора начального приближения x 0 (сложность оценки области сходимости метода); 2. Необходимость на каждом итерационном шаге вычислять помимо f(x k ) также и ее производную f'(x k ). Для частичного решения первой проблемы предлагают видоизменить формулу метода, добавив коэффициент α k <1 1 ( ) '( ) k k k i k f x x x f x Вначале выбирают минимальное значение i=0, 1, 2, … и α i ≈ 1 2 i , удовлетворяющее условиям сходимости Факт сходимости устанавливается экспериментально. После осуществления достаточного 158 количества итераций, когда оказывается |x k - x | σ, переходят к основной формуле метода, полагая α i =1. Вторая проблема снимается, если положить f '(x k )=f '(x 0 ). Однако в этом случае скорость сходимости становится линейной. Иногда сложно, а порой и невозможно, получить аналитическое выражение производной. Тогда имеет смысл использовать её конечно- разностную аппроксимацию: ( ) ( ) '( ) , k k k k k f z f x f x z x где k k z x Если 1 k k z x , формула метода приобретает вид 1 1 1 ( ) ( ) ( ) k k k k k k k k x x x x f x f x f x Метод становится двухшаговым. Его название – метод секущих. Порядок сходимости 5 1 2 p В методе Стеффенсона полагают ( ) k k k z x f x . Условие k k z x выполняется, если приближение k x близко к корню. Этот метод одношаговый, скорость его сходимости p=2. Метод ложного положения получают, если k z c , где с фиксированная точка в окрестности корня. Скорость сходимости метода линейная. Доп. замечания. 1.При каких условиях сходимость метода становится глобальной? Утверждение. Пусть уравнение f(x)=0 имеет корень x , функция f(x) дважды непрерывно дифференцируема на всей числовой оси, а её первая и вторая производные знакопостоянны. Тогда метод Ньютона сходится при любом начальном приближении x 0 , причем, начиная с к=1, последовательность сходится монотонно с той стороны от корня, где f(x) f''(x) >0. 159 2.Уточнение метода Ньютона для случая кратного корня. В принципе для вычисления корня уравнения f(x) =0 кратности m можно использовать стандартный метод Ньютона. Однако в этом случае скорость сходимости оказывается только линейной, причём знаменатель соответствующей геометрической прогрессии 1 1 q m . Для сохранения квадратичной скорости сходимости метод нужно модифицировать следующим образом 1 ( ) , '( ) k k k k f x x x m f x k 0. |