lopt9 (Лекционный курс)
Описание файла
Файл "lopt9" внутри архива находится в папке "Лекционный курс". PDF-файл из архива "Лекционный курс", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Лекция 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 .