40830

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Лекция

Информатика, кибернетика и программирование

Основные понятия и определения Выделяют четыре основные задачи линейной алгебры: решение СЛАУ вычисление определителя матрицы нахождение обратной матрицы определение собственных значений и собственных векторов матрицы. Задача отыскания решения СЛАУ с n неизвестными одна из наиболее часто встречающихся в практике вычислительных задач так как большинство методов решения сложных задач основано на сведении...

Русский

2013-10-22

1 MB

102 чел.

ТЕМА 2. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ                                        АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (СЛАУ)

2.1. Основные понятия и определения

Выделяют четыре основные задачи линейной алгебры: решение СЛАУ, вычисление определителя матрицы, нахождение обратной матрицы, определение собственных значений и собственных векторов матрицы.

Задача отыскания решения СЛАУ с n неизвестными – одна из наиболее часто встречающихся в практике вычислительных задач, так как большинство методов решения сложных задач основано на сведении их к решению некоторой последовательности СЛАУ.

Обычно СЛАУ записывается в виде

    или коротко

  .   (2.1)

Здесь А и  заданы, требуется найти *, удовлетворяющий (2.1).

Известно, что если определитель матрицы , то СЛАУ имеет единственное решение. В противном случае либо решение отсутствует (если ), либо имеется бесконечное множество решений (если ). При решении систем, кроме условия , важно чтобы задача была корректной, т.е. чтобы при малых погрешностях правой части  и (или) коэффициентов  погрешность решения  также оставалась малой. Признаком некорректности, или плохой обусловленности, является близость к нулю определителя матрицы.

Плохо обусловленная система двух уравнений геометрически соответствует почти параллельным прямым (рис. 2.1). Точка пересечения таких прямых (решение) при малейшей погрешности коэффициентов резко сдвигается. Обусловленность (корректность) СЛАУ характеризуется числом . Чем дальше  от 1, тем хуже обусловлена система. Обычно при  система некорректна и требует специальных методов решения – методов регуляризации. Приведенные ниже методы применимы только для корректных систем.

Методы решения СЛАУ делятся на прямые и итерационные.

 Прямые методы дают в принципе точное решение (если не учитывать ошибок округления) за конечное число арифметических операций. Для хорошо обусловленных СЛАУ небольшого порядка n   применяются практически только прямые методы.

Наибольшее распространение среди прямых методов получили метод Гаусса для СЛАУ общего вида, его модификация для трехдиагональной матрицы – метод прогонки и метод квадратного корня для СЛАУ с симметричной матрицей.

 Итерационные методы основаны на построении сходящейся к точному решению  рекуррентной последовательности векторов (см. подразд. 1.5)  Итерации выполняют до тех пор, пока норма разности  Последнее   берут в качестве приближенного решения.

Итерационные методы выгодны для систем большого порядка n > 1000, а также для решения плохо обусловленных систем. Многообразие итерационных методов решения СЛАУ объясняется возможностью большого выбора рекуррентных последовательностей, определяющих метод. Наибольшее распространение среди итерационных методов получили одношаговые методы простой итерации и Зейделя с использованием релаксации.

Для контроля полезно найти невязку полученного решения :

если D велико, то это указывает на грубую ошибку в расчете.

Ниже приведено описание алгоритмов указанных методов решения СЛАУ.

2.2. Прямые методы решения СЛАУ

Метод Гаусса (MG)

Метод основан на приведении с помощью преобразований, не меняющих решение, исходной СЛАУ (2.1) с произвольной матрицей к СЛАУ с верхней треугольной матрицей вида

    .     (2.2)

Этап приведения к системе с треугольной матрицей называется прямым ходом метода Гаусса.

Решение системы с верхней треугольной матрицей (2.2), как легко видеть, находится по формулам, называемым обратным ходом метода Гаусса:

  (2.3)

 Прямой ход метода Гаусса осуществляется следующим образом: вычтем из каждого m-го уравнения (m = 2 ... n) первое уравнение, умноженное на  и вместо m-го уравнения оставим полученное. В результате в матрице системы исключаются все коэффициенты первого столбца ниже диагонального. Затем, используя второе полученное уравнение, аналогично исключим элементы второго столбца (m = 3 ... n) ниже диагонального и т.д. Такое исключение называется циклом метода Гаусса. Проделывая последовательно эту операцию с расположенными ниже k-го уравнениями (k=1, 2, ..., n-1), приходим к системе вида (2.2). При указанных операциях решение СЛАУ не изменяется.

На каждом k-м шаге преобразований прямого хода элементы матриц изменяются по формулам прямого хода метода Гаусса:

    (2.4)

Элементы  называются главными. Заметим, что если в ходе расчетов по данному алгоритму на главной диагонали окажется нулевой элемент , то произойдет сбой в ЭВМ. Для того чтобы этого избежать, следует каждый цикл по k начинать с перестановки строк: среди элементов k-го столбца  находят номер p главного, т.е. наибольшего по модулю, и меняют местами строки k и p. Такой выбор главного элемента значительно повышает устойчивость алгоритма к ошибкам округления, так как в формулах (2.4) при этом производится умножение на числа , меньшие единицы, и ошибка, возникшая ранее, уменьшается.

Схема алгоритма с выбором главного элемента приведена на рис.2.2.

Проиллюстрируем метод Гаусса на решении СЛАУ 3-го порядка:

 Первый цикл: вычтем из второго уравнения первое, умноженное на , а из третьего – первое, умноженное на  получим



 Второй цикл: вычтем из третьего уравнения второе, умноженное на        a3,2/a2,2 = 0,5; получим систему с треугольной матрицей вида (2.2):

 Обратный ход: из последнего уравнения находим , подставляя во второе, находим , подставляя в первое, находим .

Таким образом, получен вектор решения

Метод прогонки (MP)

Многие задачи (например решение дифференциальных уравнений второго порядка) приводят к необходимости решения СЛАУ с трехдиагональной матрицей:

  .  (2.5)

или коротко эту систему записывают в виде

         (2.6)

В этом случае расчетные формулы метода Гаусса значительно упрощаются. После исключения поддиагональных элементов в результате прямого хода метода Гаусса и последующего деления каждого уравнения на диагональный элемент систему (2.5) можно привести к виду

  .  (2.7)

При этом формулы прямого хода для вычисления  имеют вид

    (2.8)

Когда такое преобразование (прямой ход) сделано, формулы обратного хода метода Гаусса получают в виде

       (2.9)

Расчетные формулы (2.8), (2.9) получили название «метод прогонки». Достаточным условием того, что в формулах метода прогонки не произойдет деления на ноль и расчет будет устойчив относительно погрешностей округления, является выполнение неравенства  (хотя бы для одного i должно быть строгое неравенство).

Схема алгоритма метода прогонки представлена на рис. 2.3.

Метод квадратного корня (MQ) 

Метод предназначен для решения СЛАУ с симметричной матрицей. Этот метод основан на представлении такой матрицы в виде произведения трех матриц:  где D – диагональная с элементами di=1;  S – верхняя треугольная ( если i>k, причем ); – транспонированная нижняя треугольная. Матрицу S можно по аналогии с числами трактовать как корень квадратный из матрицы A, отсюда и название метода.

Если S и D известны, то решение исходной системы  сводится к последовательному решению трех систем – двух треугольных и одной диагональной:

    .    (2.10)

Здесь .

Решение систем (2.10) ввиду треугольности матрицы S осуществляется по формулам, аналогичным обратному ходу метода Гаусса:

Нахождение элементов матрицы S (извлечение корня из А) осуществляется по рекуррентным формулам:

    ;

        (2.11)

    

В этих формулах сначала полагаем k=1 и последовательно вычисляем  и все элементы первой строки матрицы , затем полагаем k=2, вычисляем  и вторую строку  для j>2 и т.д.

Метод квадратного корня почти вдвое эффективнее метода Гаусса, т.к. полезно использует симметричность матрицы.

Схема алгоритма метода квадратного корня представлена на рис.2.4. Функция sign(x) возвращает –1 для всех x<0 и +1 для всех x>0.



Проиллюстрируем метод квадратного корня, решая систему трех уравнений:

   .   (2.12)

Нетрудно проверить, что матрица A есть произведение двух треугольных матриц (здесь ):

.

Исходную систему запишем в виде

.

Обозначим

.

Тогда для вектора  получим систему :

.

Зная , решаем систему :

.

2.3. Итерационные методы решения СЛАУ

Метод простой итерации (MI)

В соответствии с общей идеей итерационных методов (см. подразд. 1.5) исходная система (2.1) должна быть приведена к виду, разрешенному относительно :

   ,      (2.13)

где G – матрица;  – столбец свободных членов.

При этом решение (2.13) должно совпадать с решением (2.1). Затем строится рекуррентная последовательность первого порядка в виде

.

Для начала вычислений задается некоторое начальное приближение  (например , для окончания – некоторое малое . Получаемая последовательность будет сходиться к точному решению, если норма матрицы  (см. подразд. 1.5).

Привести исходную систему к виду (2.13) можно различными способами, например:

Здесь E – единичная матрица; a – некоторый параметр, подбирая который можно добиться, чтобы

В частном случае, если исходная матрица A имеет преобладающую главную диагональ, т.е. , то преобразование (2.1) к (2.13) можно осуществить просто, решая каждое i-е уравнение относительно . В результате получим следующую рекуррентную формулу:

  ,    (2.14)

   .

Схема алгоритма представлена на рис. 2.5.

Приведем пример решения методом простой итерации следующей системы трех уравнений:

         (2.15)

Преобразуем ее к виду (2.13), для чего из первого уравнения выразим , из второго  и из третьего  и получим рекуррентную формулу

    (2.16)

Зададим начальное приближение , подставим в правую часть (k = 1), получим :  ().

Подставляя полученные значения снова в (2.16) (k = 2), получим :



= (1.075; 1.3; 1.175).

Вычислим погрешность на второй итерации:

Если , то процесс продолжаем.

Метод Зейделя (MZ)

Метод Зейделя является модификацией метода простой итерации. Суть его состоит в том, что при вычислении очередного приближения  в формуле (2.14) используются вместо  уже вычисленные ранее  т.е. (2.14) преобразуется к виду

      (2.17)

Такое усовершенствование позволяет ускорить сходимость итераций почти в два раза. Кроме того, данный метод может быть реализован на ЭВМ без привлечения дополнительного массива, т. к. полученное новое  сразу засылается на место старого.

Схема алгоритма аналогична схеме метода простой итерации (см. рис.2.5), если x0j заменить на xj и убрать строки x0i=1,  x0i=xi.

Для иллюстрации решим систему (2.15) методом Зейделя. Разрешая ее, относительно , аналогично (2.16) получаем рекуррентную формулу (2.17) вида

         (2.18)

Зададим, как и в методе простой итерации, начальное условие , подставим в первое уравнение, получаем  При вычислении  это значение сразу используем: , аналогично  получаем . Для второй итерации:

  

 Погрешность после двух итераций  меньше, чем в методе простой итерации.

2.4. Понятие релаксации

Методы простой итерации и Зейделя сходятся примерно так же, как геометрическая прогрессия со знаменателем . Если норма матрицы G близка к 1, то сходимость очень медленная. Для ускорения сходимости используется метод релаксации. Суть его в том, что полученное по методу простой итерации или Зейделя очередное значение  пересчитывается по формуле

    .     (2.19)

Здесь 0 <   2параметр релаксации.

Если < 1 – нижняя релаксация, если > 1 – верхняя релаксация. Параметр  подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.

Схема алгоритма на рис. 2.5 выполнена с использованием релаксации.

2.5. Варианты заданий

Составить программу решения СЛАУ порядка n и решить систему линейных уравнений пятого порядка с трехдиагональной симметричной матрицей вида

.

Значения q и d заданы в табл. 2.1.  

В вариантах, использующих прямые методы вычислить невязку (см.            подразд. 2.1).

В вариантах, использующих итерационные методы, построить график зависимости количества итераций it, необходимых для достижения заданной точности, от параметра релаксации и установить, при каком значении число итераций минимально. Параметр релаксации менять от 0.2 до 2 с шагом 0.2.

                                             Таблица 2.1

№ вар.

Mетод

d

q

e

1

MG

–1

–4.25

2

MI

1

–3.17

10–3

3

MQ

–2

–3.23

4

MZ

2

–2.57

10–4

5

MP

–3

–4.67

6

MI

3

–2.23

10–4

7

MG

–4

–2.75

8

MI

4

–2.25

10–4

9

MQ

–5

–2.85

10

MZ

5

–2.24

10–5

11

MP

–6

–3.83

12

MZ

6

–2.17

10–4

13

MG

–7

–2.86

14

MI

7

–3.14

10–3

15

MQ

8

4.88

2.6. Контрольные вопросы

1. Что понимается под корректностью СЛАУ?

2. Решите по методу Гаусса заданную систему из трех уравнений.

3. В чем суть метода квадратного корня?

4. Когда используются методы прогонки и квадратного корня?

5. Решите заданную систему трех уравнений методом простой итерации и методом Зейделя.

6. Для чего нужна релаксация? Ее суть.

PAGE  23


 

А также другие работы, которые могут Вас заинтересовать

75905. Почему большевики смогли взять и удержать власть 15.43 KB
  Напротив большевики придя к власти незамедлительно приняли Декрет о земле отменивший право частной собственности на землю: земля переходила во всенародную государственную собственность; В 1914-1918 гг. Большевики соответственно также издали и Декрет о мире; Политическая раздробленность царившая среди остальных партийных кругов компромисс кадетов с эсерами с меньшевиками привела к потере ими фактического влияния в стране; наиболее организованной группой оставались лишь большевики способные в короткий срок мобилизовать собственные...
75906. Диссидентское движение в СССР: основные направления, лидеры и результаты деятельности 19.6 KB
  Диссиденты (лат. dissidents - несогласный) - термин, который с середины 70-х годов применялся к лицам, открыто спорившим с официальными доктринами в тех или иных областях общественной жизни СССР и пришедшим к явному столкновению с аппаратом власти. Первые годы брежневского правления
75907. Сравнительный анализ политических программ двух-трех современных российских политических партий (целевая аудитория (электорат) партии, образ желаемого будущего России (политическая, социально-экономическая модели, место России в международных процессах) 16.93 KB
  Все три партии видят будущее России поразному. Окончательное формирование социалистических общественных отношений В качестве альтернативы этим шагам предусмотрена программаминимум которая предполагает национализацию природных богатств России установление власти трудящихся и т. В программе ЕР нет ясного положения относительно будущего России какой она должна быть отсутствует там и идеология партии.
75908. Аграрная политика в дореволюционной России и в СССР: крепостное право и коллективизация без выдачи паспортов, община и колхоз 16.6 KB
  Крепостное право и кресьянская община. В России крестьянская община зародилась вместе с Древнерусским государством и видоизменяясь просуществовала вплоть до конца 1920х. В период Киевской Руси крестьянская община стала основной производящей единицей.
75909. В чем причины кризиса советской экономики в 1980-е гг.? Системный кризис, падение цен на нефть, нерентабельность производства, экстенсивный характер развития? Причины субъективные и объективные 15.55 KB
  Системный кризис падение цен на нефть нерентабельность производства экстенсивный характер развития Причины субъективные и объективные. Проблемы экономического развития были вызваны рядом причин: Системный кризис. В условиях догоняющего развития без демократических свобод при отсутствии гражданского общества в СССР произошла подмена цели средствами главной жертвой которой стала свобода как необходимое хотя и не единственное условие развития человека его инициативы и предприимчивости. Советская модель хозяйствования лишенная...
75910. Как характеризуют существовавшие в конце 80-х - начале 90-х программы реформ Г.Явлинский и А.Чубайс? Каковы отличия в подходах и восприятии 18.19 KB
  Российская приватизация по масштабам и объему стоящих перед ней задач принципиально отличалась от приватизации осуществленной в 1980е годы в странах Запада.Чубайс прохладно относился к приватизации однако понимал важность ее осущетсвления в рамках проведения рыночных реформ. списка литры: мы вели очень жесткую теоретическую дискуссию с Виталием Найшулем как автором концепции ваучерной приватизации приводили ему длинный список катастрофических тяжелейших последствий которые она неизбежно повлечет за собой. мне лично тема приватизации...
75911. Особенности шоковой терапии и приватизации в России 18.04 KB
  Особенности процесса приватизации происходившего в России: массовый характер приватизации вызванный высокой долей государственной собственности в стране а также стремлением ускорить процесс преобразования экономической структуры общества; значительный удельный вес неэквивалентных форм безвозмездная передача оплата не в полной мере и др. вызванный отсутствием денежных средств в частных руках; проведение особого ваучерного этапа приватизации. Целью приватизации провозглашалось создание эффективного собственника однако бесплатная...
75912. Российские экономические реформы 1990-х гг. в оценках западных исследователей: направления критики 19.84 KB
  В оценках западных исследователей: направления критики Негативная оценка результатов российских реформ общее в выступлениях экономистов Оправдывать или объяснять логику развития событий в России становится неприличным и социально опасным Российские реформы далеки от того чтобы считать их феноменально успешными Главные аргументы критиков Игнорирование китайского опыта...
75913. Понятие «модернизация». Что подразумевают под «европейской модернизацией» России? Какие исторические формы этот процесс приобретал? Можно ли считать сталинскую индустриализацию модернизацией 16.6 KB
  Что подразумевают под европейской модернизацией России Какие исторические формы этот процесс приобретал Можно ли считать сталинскую индустриализацию модернизацией Модернизация современный термин используемый для характеристики давно уже идущего в мире процесса процесса социальных изменений посредством которых менее развитые общества приобретают характеристики отличающие большинство развитых обществ. Несмотря на то что исторически многие страны в своем развитии шли бок о бок термин модернизация долгое время не использовался....