Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 3
Текст из файла (страница 3)
Однородная система (25) с диагональным преобладанием имеет толькотривиальное решение.2. Определитель матрицы A с диагональным преобладанием не равен нулю.3. Неоднородная система (1) с диагональным преобладанием всегда разрешима ипритом единственным образом.Последнее из них означает, что доказательство теоремы завершено.1.4. Системы с трехдиагональной матрицей. Метод прогонки.При решении многих задач приходится иметь дело с системами линейныхуравнений вида:Ai xi −1 + Ci xi + Bi xi +1 = Fi , i = 1,..., n − 1 ,(28)x0 = q0 , xn = qn ,(29)-8где коэффициенты Ai , Ci , Bi , правые части Fi (i = 1,K, n − 1) известны вместе с числамиq0 и qn . Дополнительные соотношения (29) часто называют краевыми условиями длясистемы (28). Во многих случаях они могут иметь более сложный вид.
Например:x0 = p0 x1 + q0 ; xn = pn xn −1 + qn ,где p0 , q0 , pn , qn - заданные числа. Однако, чтобы не усложнять изложение, мыограничимся простейшей формой дополнительных условий (29).Пользуясь тем, что значения x0 и xn заданы, перепишем систему (28) в виде:C1 x1 + B1 x2= F1 − A1q0A2 x1 + C2 x2 + B1 x3 = F2(30)MAn −1 xn −2 + Cn −1 xn−1 = Fn −1 − Bn−1qnМатрица этой системы имеет трёхдиагональную структуру:0 ⎤⎡ C1 B1 0 0 L 0⎢A C B0 L 00 ⎥22⎢ 2⎥0 ⎥(31)⎢ 0 A3 C3 B3 L 0⎢K K K K K KK ⎥⎥⎢⎢⎣ 0 0 0 0 K An−1 Cn−1 ⎥⎦Это существенно упрощает решение системы (28) благодаря специальному методу,получившему название метода прогонки.Метод основан на предположении, что искомые неизвестные xi и xi +1 связанырекуррентным соотношениемxi = αi +1 xi +1 + β i +1 , 0 ≤ i ≤ n − 1 .(32)Здесь величины α i +1 , β i +1 , получившие название прогоночных коэффициентов,подлежат определению, иcходя из условий задачи (28), (29).
Фактически такаяпроцедура означает замену прямого определения неизвестных xi задачей определенияпрогоночных коэффициентов с последующим расчетом по ним величин xi .Для реализации описанной программы выразим с помощью соотношения (32) xi −1через xi +1 :xi −1 = αi xi + β i = α iα i +1 xi +1 + α i β i +1 + β iи подставим xi −1 и xi , выраженные через xi +1 , в исходные уравнения (28). В результатеполучим:( Aiα iα i +1 + Ciαi +1 + Bi ) xi +1 + Aiαi β i +1 + Ai β i + Ci β i +1 − Fi = 0 ,i = 1, 2,K n − 1 .Последние соотношения будут заведомо выполняться и притом независимо отрешения, если потребовать, чтобы при i = 1, 2,K n − 1 имели место равенства:Aiα iα i +1 + Ciα i +1 + Bi = 0,Aiα i β i +1 + Ai β i + Ci β i +1 − Fi = 0.Отсюда следуют рекуррентные соотношения для прогоночных коэффициентов:-9− BiF − Ai β i, β i +1 = i, i = 1, 2,K n − 1 .(33)Aiα i + CiAiα i + CiЛевое граничное условие x0 = q0 и соотношение x0 = α1 x1 + β1 непротиворечивы,если положитьα1 = 0, β1 = q0 .(34)Остальные значения коэффициентов прогонки α 2 ,K,α n и β 2 ,K, β n находим из (33),чем и завершаем этап вычисления прогоночных коэффициентов.Далее, согласно правому граничному условиюxn = qn .(35)Отсюда можно найти остальные неизвестные xn −1 ,K x1 в процессе обратной прогонки спомощью рекуррентной формулы (32).Число операций, которое требуется для решения системы общего вида (1)методом Гаусса, растет при увеличении n пропорционально n 3 .
Метод прогонкисводится к двум циклам: сначала по формулам (33) рассчитываются прогоночныекоэффициенты, затем с их помощью по рекуррентным формулам (32) находятсякомпоненты решения системы xi . Это означает, что с увеличением размеров системычисло арифметических операций будет расти пропорционально n , а не n 3 . Такимобразом, метод прогонки в пределах сферы своего возможного применения являетсясущественно более экономичным.
К этому следует добавить особую простоту егопрограммной реализации на компьютере.Во многих прикладных задачах, которые приводят к СЛАУ с трехдиагональнойматрицей, ее коэффициенты удовлетворяют неравенствам:Ci > Ai + Bi ,(36)которые выражают свойство диагонального преобладания. В частности, мы встретимтакие системы в третьей и пятой главе.Согласно теореме предыдущего раздела решение таких систем всегда существуети является единственным.
Для них также справедливо утверждение, которое имеетважное значение для фактического расчета решения с помощью метода прогонки.α i +1 =ЛеммаЕсли для системы с трехдиагональной матрицей выполняется условие диагональногопреобладания (36), то прогоночные коэффициенты удовлетворяют неравенствам:αi ≤ 1 .(37)Доказательство проведем по индукции. Согласно (34) α1 = 0 , т. е. при i = 1утверждение леммы верно. Допустим теперь, что оно верно для α i и рассмотрим α i +1 :BiBi≤≤ 1.(38)Ci + AiαiCi − AiИтак, индукция от i к i + 1 обоснована, что и завершает доказательство леммы.Неравенство (37) для прогоночных коэффициентов α i делает прогонкуустойчивой. Действительно, предположим, что компонента решения xi в результатепроцедуры округления рассчитана с некоторой ошибкой.
Тогда при вычисленииαi +1 =- 10 следующей компоненты xi −1 по рекуррентной формуле (32) эта ошибка, благодарянеравенству (37), не будет нарастать.§2. Обусловленность СЛАУ.Серьезным препятствием при решении систем линейных алгебраическихуравнений может оказаться возможность заметного отклонения приближенногорешения от точного из-за незначительных возмущений правых частей уравнений,которые неизбежно возникают в приближенных вычислениях. Причиной такогонежелательного эффекта часто оказывается так называемая плохая обусловленностьматрицы системы линейных уравнений.2.1. Норма матрицы.Рассмотрим линейное вещественное евклидово пространство E n , элементамикоторого являются вектора в виде упорядоченной системы n чисел x = {x1 ,K xn } . Впространстве E n определены скалярное произведение(x, y ) = x1 y1 + K + xn yn(39)и евклидова нормаx = ( x, x ) = x12 + K + xn2 ,(40)удовлетворяющая трем аксиомам нормы:1.
x ≥ 0 , x = 0 тогда и только тогда, когда x = 0 ;2. α x = α x ∀α , x ;3. x + y ≤ x + y (неравенство треугольника).Для скалярного произведения справедливо неравенство Коши-Буняковского( x, y ) ≤ x y .Рассмотрим квадратную матрицу A размером n × n . Она определяет впространстве E n линейное преобразованиеy = Ax(41)илиny i = ∑ a ij x j , i = 1, K , n .j =1Введем величинуAx,(42)xx ≠0которую принято называть нормой матрицы A , согласованной с нормой вектора x .Записывая ненулевой вектор x в видеx = x z,где z вектор единичной длины: z = 1 , получим представление для нормы,эквивалентное (42)A = sup Az .(43)A = supz =1- 11 Отсюда следует, что в конечномерном пространстве норма матрицы ограничена,причем на единичной сфере всегда найдется такой вектор z 0 , чтоA = Az 0 .Наконец, из определения нормы (42) следует, чтоAx ≤ A ⋅ x .(44)Это простое неравенство лежит в основе всех дальнейших оценок.2.2.
Корректность решения СЛАУ.Следуя Адамару, будем называть математическую задачу корректной, есливыполняются три условия:1. Решение задачи существует.2. Решение задачи единственное.3. Решение задачи непрерывно зависит от входных данных.Обсудим с точки зрения этого определения задачу решения СЛАУ с неравнымнулю определителемAx = f ,(45)считая матрицу A фиксированной и рассматривая в качестве входных данных векторправых частей системы f = { f1 , f 2 ,K, f n } ∈ En .Условие ∆ ≠ 0 гарантирует существование у матрицы A обратной матрицы A−1 ,через которую решение системы (45) можно записать в видеx = A−1f .(46)Пусть теперь правая часть подверглась возмущению δ f и стала равной f% = f + δ f .Тогда, согласно (46), решение x% возмущенной системы(47)Ax% = f%−1тоже можно записать через обратную матрицу A :(48)x% = A−1f% = A−1f + A−1δ f = x + δ x ,гдеδ x = A−1δ f .(49)Отсюда получаем(50)δ x ≤ A−1 δ f .Неравенство (50) доказывает непрерывную зависимость возмущения решения δ x отвозмущения правой части δ f :δ x → 0 при δ f → 0 .(51)Это означает, что решение СЛАУ с неравным нулю определителем ∆ - корректнаяматематическая задача: для нее выполняются все три требования корректностиАдамара.2.3.
Число обусловленности матрицы.Исходное уравнение (45) позволяет написать неравенство:f ≤ A x .Перемножая его с неравенством того же знака (50), получим:(52)- 12 f δ x ≤ A A −1 x δ f .(53)Пусть f ≠ 0 , тогда, согласно (46), x ≠ 0 и неравенство (53) можно переписать в виде:δxδf≤ MA,(54)xfгде(55)M A = A ⋅ A−1 .Число M A называется числом обусловленности матрицы A . Оно позволяет оценитьотносительную погрешность решения через относительную погрешность возмущенияправой части.
Поскольку исходная система (45) линейная, оценка относительнойпогрешности является более естественной, чем оценка абсолютной погрешности. Чембольше M A , тем резче реагирует решение на возмущение правой части. Поэтомуматрицы с большим числом обусловленности и соответствующие им СЛАУ называютплохо обусловленными.
Для оценки роли, которую играет число обусловленности прирешении линейных алгебраических систем, разберем задачу.Задача 1Рассмотреть систему двух уравненийx1 + 0 ⋅ x2 = 1⎡1 0 ⎤, A= ⎢(56)⎥ , f = {1,1}x1 + 0.01 ⋅ x2 = 1⎣1 0.01⎦и соответствующую ей возмущенную системуx1 + 0 ⋅ x2 = 1⎡1 0 ⎤ %, A= ⎢(57)⎥ , f = {1,1.01}.x1 + 0.01 ⋅ x2 = 1.01⎣1 0.01⎦Выписать решения этих систем, подсчитать погрешность возмущения правой частии соответствующую ей погрешность возмущения решения. Найти числообусловленности матрицы A , составить с его помощью теоретическую оценкупогрешности (54) и сравнить результат с результатом, полученнымнепосредственно по известным решениям систем.В данном случае определитель матрицы A отличен от нуля∆ = det A = 0.01 ,т.
е. обе системы невырожденные. Система (57) отличается от системы (56)возмущением правой частиf = {1,1} , f = 2 , f% = {1,1.01} , δ f = {0,0.01} , δ f = 0.01 .Решения систем (56) и (57) имеют вид:x = {1,0} , x = 1 , x% = {1,1} , δ x = {0,1} , δ x = 1 .При этомδ f 0.01 δ x=,= 1.(58)fx2Мы видим, что небольшое относительное возмущение правой части привело ксильному возмущению решения: относительная погрешность решения равна единице.Этот результат означает, что исходная система плохо обусловлена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
