lopt9 (1013504)
Текст из файла
Лекция 9Раздел II. ЧИСЛЕННЫЕ МЕТОДЫ1. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХАЛГЕБРАИЧЕСКИХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИРассматривается проблема решения систем линейных алгебраических уравнений(СЛАУ), записываемых в видеAx = bили⎛ a11 " a1n ⎞ ⎛ x1 ⎞ ⎛ b1 ⎞⎟⎜ ⎟ ⎜ ⎟⎜⎜ # % # ⎟ ⎜ # ⎟ = ⎜ # ⎟,⎟⎜ ⎟ ⎜ ⎟⎜a⎝ n1 " ann ⎠ ⎝ x n ⎠ ⎝ bn ⎠где A = (ai j ) ∈ R n × n – действительная матрица размеров (n × n) , i , j – переменные, соответствующие номерам строк и столбцов (целые числа); b = (b1 ,..., bn )T ∈ R n – векторстолбец размеров (n × 1) , x = ( x1 ,..., x n )T ∈ R n – вектор-столбец неизвестных, R n – n мерное евклидово пространство, верхний индекс "T " здесь и далее обозначает операциютранспонирования.Требуется найти решение x ∗ = ( x ∗1 ,..., x ∗ n )T ∈ R n системы, подстановка которогов систему приводит к верному равенству A x ∗ = b .З а м е ч а н и я.1.
Из курса линейной алгебры известно, что решение задачи существует и единственно, если определитель (детерминант) матрицы A отличен от нуля, т.е. det A ≡ A ≠ 0( A – невырожденная матрица, называемая также неособенной).Классификация численных методов решения СЛАУПри решении СЛАУ используются два класса численных методов:1.
Прямые методы, позволяющие найти решение за определенное число операций.К прямым методам относятся: метод Гаусса и его модификации (в том числе метод прогонки), метод LU – разложения и др. Изучаются в курсе линейной алгебры.2. Итерационные методы, основанные на использовании повторяющегося (циклического) процесса и позволяющие получить решение в результате последовательныхприближений. Операции, входящие в повторяющийся процесс, составляют итерацию.К итерационным методам относятся: метод простых итераций, метод Зейделя и др.ИТЕРАЦИОННЫЕ МЕТОДЫА.
МЕТОД ПРОСТЫХ ИТЕРАЦИЙАльтернативой прямым методам являются итерационные методы, основанные намногократном уточнении x (0) – приближенно заданного решения задачи A x = b . Верх-74ним индексом в скобках здесь и далее по тексту обозначается номер итерации (совокупности повторяющихся действий).Методика решения задачиШаг 1. Исходная задача A x = b преобразуется к равносильному виду:x = α x + β,где α = { α ij } – квадратная матрица, β = { β i } – вектор, i, j = 1,..., n .
Это преобразованиеможет быть выполнено различными путями, но для обеспечения сходимости итераций(см. процедуру 2) нужно добиться, чтобы α < 1 (чтобы норма α была меньше единицы.Понятие нормы вводится ниже.)Шаг 2. Вектор β принимается в качестве начального приближения x (0) = β и далее многократно выполняются действия по уточнению решения согласно рекуррентномусоотношениюx ( k +1) = α x ( k ) + β,k = 0,1,...или в развернутом видеx1(k +1) = α11 x1(k ) + α12 x 2(k ) + ...
+ α1n x n(k ) + β1 ,x 2(k +1) = α 21 x1(k ) + α 22 x 2(k ) + ... + α 2n x n(k ) + β 2 ,#x n(k +1) = α n1 x1(k ) + α n 2 x 2(k ) + ... + α nn x n(k ) + β n .Шаг 3. Итерации прерываются при выполнении условияx (k +1) − x (k ) < ε ,где ε > 0 – заданная точность, которую необходимо достигнуть при решении задачи.З а м е ч а н и я.1.
Процесс называется параллельным итерированием, так как для вычисления(k + 1) -го приближения всех неизвестных учитываются вычисленные ранее их k -е приближения.2. Начальное приближение x (0) может выбираться произвольно, или из некоторыхсоображений, например x (0) = β . При этом может использоваться априорная информация о решении или просто «грубая» прикидка.75Нормы матриц и векторовНаиболее употребительными являются следующие формулы для вычисления значений норм матриц и векторов, образованных действительными компонентами.Нормы матрицы A1)2)3)A1= maxn∑Нормы вектора xaij ;x= max ∑ aij ;xij =1= max x i ;1inAA23j=2i =1nn∑ ∑ aij2 ;=x3i =1 j =1n∑i =1=xi ;n∑ xi2 .i =1Скорость сходимости{ }Рассмотрим последовательность x (k ) , сходящуюся к x ∗ . Предположим, что всеее элементы различны и ни один из них не совпадает с x ∗ . Наиболее эффективный способ оценивания скорости сходимости состоит в сопоставлении расстояния между x (k +1)и x ∗ с расстоянием между x (k ) и x ∗ .{ }Последовательность x (k )симальное число, для которогоназывается сходящейся с порядком p , если p – мак-0 ≤ limk →∞x (k +1) − x ∗x(k )− x∗p< ∞.Поскольку величина p определяется предельными свойствамивается асимптотической скоростью сходимости.{ x } , она назы(k ){ }Если последовательность x (k ) – сходящаяся с порядком p , то числоc = limk →∞x (k +1) − x ∗x (k ) − x ∗pназывается асимптотическим параметром ошибки.Если p = 1 , c < 1 , то сходимость линейная, если p = 2 – квадратичная, если p = 3– кубичная и т.д.
Если p > 1 или p = 1, c = 0 , то сходимость сверхлинейная. Линейнаясходимость является синонимом сходимости со скоростью геометрической прогрессии.Сверхлинейная сходимость является более быстрой, чем определяемая любой геометрической прогрессией.76Теоремы о сходимостиТеорема (о достаточном условии сходимости метода простых итераций).
Методпростых итераций, реализующийся в процессе последовательных приближений, сходится к единственному решению исходной системы Ax = b при любом начальном приближении x (0) со скоростью не медленнее геометрической прогрессии, если какая-либонорма матрицы α меньше единицы, т.е.
α s < 1 ( s ∈ { 1,2,3 } ).З а м е ч а н и я.1. Сходящийся процесс обладает свойством самоисправляемости, т.е. отдельнаяошибка в промежуточных вычислениях не отразится на окончательном результате, таккак ошибочное приближение можно рассматривать как новое начальное.2. Условия сходимости выполняются, если в матрице A диагональные элементыпреобладают, т.е.aii ≥ ai1 + ... + ai ,i −1 + ai ,i +1 + ... + ain , i = 1,..., n ,и хотя бы для одного i неравенство строгое. Иначе, модули диагональных коэффициентов в каждом уравнении системы больше суммы модулей недиагональных коэффициентов (свободные члены не рассматриваются).3. Чем меньше величина нормы α , тем быстрее сходимость метода.Способы преобразования системыПреобразование системы Ax = b к виду x = αx + β с матрицей α , удовлетворяющей условиям сходимости, может быть выполнено несколькими способами.
Приведемспособы, используемые наиболее часто.1. Уравнения, входящие в систему Ax = b , переставляются так, чтобы выполнялось условие преобладания диагональных элементов (для той же цели можно использовать другие элементарные преобразования). Затем первое уравнение разрешается относительно x1 , второе – относительно x 2 и т.д. При этом получается матрица α с нулевымидиагональными элементами.Например, система− 2,8x1 + x 2 + 4 x 3 = 60 ,10 x1 − x 2 + 8 x 3 = 10 ,− x1 + 2 x 2 − 0,6 x 3 = 20с помощью перестановки уравнений приводится к виду10 x1 − x 2 + 8 x 3 = 10 ,− x1 + 2 x 2 − 0,6 x 3 = 20 ,− 2,8x1 + x 2 + 4 x 3 = 60 ,где 10 > − 1 + 8 , 2 > − 1 + − 0,6 , 4 > − 2,8 + 1 , т.е.
диагональные элементы преобладают.77Выражая x1 из первого уравнения, x 2 – из второго, а x 3 – из третьего, получаемсистемуx1 = 0 ⋅ x1 + 0,1x 2 − 0,8x 3 + 1 ,x 2 = 0,5x1 + 0 ⋅ x 2 + 0,3x 3 + 10 ,x 3 = 0,7 x1 − 0,25x 2 + 0 ⋅ x 3 + 15 ,0,1− 0,8 ⎞⎛ 0⎛1⎞⎟⎜⎜ ⎟где α = ⎜ 0,500,3 ⎟ , β = ⎜10 ⎟ .⎜ 0,7 − 0,25⎜15 ⎟0 ⎟⎠⎝⎝ ⎠Заметим, что α1= max { 0,9 ; 0,8 ; 0,95 } = 0,95 < 1 , т.е. условие теоремы выполне-но.Проиллюстрируем применение других элементарных преобразований. Так, система4 x1 + x 2 + 9 x 3 = − 7 ,3x1 + 8x 2 − 7 x 3 = − 6 ,x1 + x 2 − 8 x 3 = 7путем сложения первого и третьего уравнений и вычитания из второго уравнения третьего уравнения преобразуется к виду5x1 + 2 x 2 + x 3 = 0 ,2 x1 + 7 x 2 + x 3 = −13 ,x1 + x 2 − 8x 3 = 7с преобладанием диагональных элементов.2.
Уравнения преобразуются так, чтобы выполнялось условие преобладания диагональных элементов, но при этом коэффициенты α ii не обязательно равнялись нулю.Например, систему1,02 x1 − 0,15 x 2 = 2,7 ,0,8 x1 + 1,05 x 2 = 4можно записать в формеx1 = − 0,02 x1 + 0,15 x 2 + 2,7 ,x 2 = − 0,8 x1 − 0,05 x 2 + 4 ,для которой α{ εij }1= max { 0,17 ; 0,85 } = 0,85 < 1 .3. Если det A ≠ 0 , систему Ax = b следует умножить на матрицу D = A −1 − ε , где– матрица с малыми по модулю элементами. Тогда получается система78( A −1 − ε) Ax = D bA −1 A x − εA x = D b , которую можно записать в формеилиx = αx + β , где α = ε A , β = D b . Еслиε ij , i, j = 1,..., n , достаточно малы, условиесходимости выполняется.Б.
МЕТОД ЗЕЙДЕЛЯЭтот метод является модификацией метода простых итераций и в некоторых случаях приводит к более быстрой сходимости.Итерации по методу Зейделя отличаются от простых итераций тем, что при нахождении i -й компоненты (k + 1) -го приближения сразу используются уже найденныекомпоненты (k + 1) -го приближения с меньшими номерами 1,2,..., i − 1 . При рассмотрении развернутой формы системы итерационный процесс записывается в видеx1( k +1) = α11 x1(k ) + α12 x 2( k ) + α13 x 3( k ) + ...
+ α1n x n(k ) + β1 ,x 2( k +1) = α 21 x1( k +1) + α 22 x 2(k ) + α 23 x 3(k ) + ... + α 2n x n( k ) + β 2 ,(1.1)x 3( k +1)=α 31 x1( k +1)+α 32 x 2( k +1)+α 33 x 3( k )+ ... + α 3n x n( k ) + β3 ,#x n( k +1) = α n1 x1(k +1) + α n 2 x 2( k +1) + α n3 x 3( k +1) + ... + α nn −1 x n(k−+11) + α nn x n(k ) + β n .В каждое последующее уравнение подставляются значения неизвестных, полученных из предыдущих уравнений, что показано в записи стрелками.Теорема о сходимостиТеорема (о достаточном условии сходимости метода Зейделя).Если для системы x = αx + β какая-либо норма матрицы α меньше единицы,т.е. α s < 1 ( s ∈ { 1,2,3 } ), то процесс последовательных приближений сходитсякединственному решению исходной системы Ax = b при любом начальном приближенииx (0 ) .Записывая (1.1) в матричной форме, получаемx (k +1) = Lx (k +1) + Ux (k ) + β ,где L,U являются разложениями матрицы α :79(1.2)⎛ 0⎜⎜ α 21L = ⎜ α 31⎜⎜"⎜⎝ α n100"00""α 32"α n20" "α n3 "⎛ α11⎜⎜ 0U =⎜ 0⎜⎜"⎜⎝ 00⎞⎟0⎟0 ⎟,⎟"⎟⎟0⎠α12α13α 22α 23α 33"00"0" α1n ⎞⎟" α 2n ⎟" α 3n ⎟ .⎟" " ⎟⎟" α nn ⎠Преобразуя (1.2) к виду x = αx + β , получаем матричную форму итерационногопроцесса метода Зейделя:−1−1x ( k +1) = ( E − L ) U x ( k ) + ( E − L ) β .(1.3)З а м е ч а н и я.1.
Для обеспечения сходимости метода Зейделя требуется преобразовать системуAx = b к виду x = αx + β с преобладанием диагональных элементов в матрице α (см.метод простых итераций).Например, в системе2 x1 + x 2 = 2 ,x1 − 2 x 2 = −2диагональные элементы преобладают, так как 2 > 1 , − 2 > 1 .Соотношения метода Зейделя (1.1) принимают видx1(k +1)x 2(k +1)=−=x 2(k )2x1(k +1)2+ 1,+ 1.Выберем в качестве начального приближения x (0) = (0 ; 0)T(рис.1,а). Тогдаx 2(0)+ 1 = 1 .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
