40830

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

Лекция

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

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

Русский

2013-10-22

1 MB

104 чел.

ТЕМА 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


 

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

31436. Теория двойственной истины, ее автор и сторонники. Номиналисты и реалисты в средневековой философии. Роль их спора в развитии философского знания 32.5 KB
  Поскольку Бог по сравнению с природой рассматривался как сверхбытие или высшая реальность то основное внимание должно было сосредотачиваться прежде всего на Его познании. Это значит что абсурдно утверждать реальность человечности а не конкретных людей реальность сладкого а не конкретных предметов конфет сахара шоколада и т. В самом познании они выделили различные уровни эмпирический и теоретический пытались исследовать их специфику; впервые стали рассматривать познание как процесс а не как онтологическую реальность.1 1...
31437. Общая характеристика философии эпохи Возрождения (основные направления философской мысли, представители) 43.5 KB
  Время о котором идет речь философы Возрождения называли Новым связывая его с выработкой принципиально иных подходов к развитию искусства и науки. Эпоха Возрождения это эпоха зарождения капиталистических отношений создания национальных государств и абсолютных монархий Западной Европы эпоха глубоких социальных конфликтов. Специфика философской культуры Возрождения Философская мысль эпохи Возрождения охватывает три столетия: от раннего гуманизма XIV в.
31438. Основные черты западноевропейской философии XVII века. Философия Ф. Бэкона, Т. Гоббса, Д. Локка. Философия Р. Декарта 50 KB
  В философии на первый план выдвигаются проблемы теории познания гносеологии в частности: что значит знать что пролагает дорогу к истине ощущения или разум интуиция или логика аналитическим или синтетическим должно быть познание и т. Одна группа работ посвящена проблемам развития науки и анализа научного познания. Основной задачей философии Бэкон считал конструирование нового метода познания а целью науки принесение пользы человечеству. Фундаментом всякого познания по оценке Бэкона является опыт который должен быть...
31439. Основные черты западноевропейской философии XVIII века. Философские взгляды просветителя Ж.-Ж. Руссо. Утопический социализм Сен-Симона и Оуэна. Философия французского материализма XVIII века (Дидро, Гельвеции, Гольбах) 39 KB
  Руссо. Второй этап с середины 40х годов до конца 80х годов до Французской революции: Руссо Кондильяк и четыре великих французских материалиста Ламетри Дидро Гельвеций и Гольбах. К материалистам относятся вышеупомянутые четыре французских материалиста деистическую религию исповедовал Вольтер; новую разновидность подхода к христианству религию чувства развивал Руссо. Большинство просветителей склонялись к идеям реформизма меньшинство например Мелье Руссо были революционерами.
31440. Немецкая классическая философия: Кант, Фейербах 31 KB
  Для Канта этот вопрос сводится к вопросу о возможности чистой математики и чистого естествознания см. Кант Родоначальником немецкой классической философии стал Иммануил Кант 17241804 В философии Канта выделяется два периода:1 докритический и 2 критический. На первом этапе Кант выступает материалистом.
31441. Немецкая классическая философия: Гегель 24 KB
  Самораскрытие Абсолютного Духа в пространстве это природа; самораскрытие во времени история. Историю движут противоречия между национальными духами которые суть мысли и проекции Абсолютного Духа. Когда у Абсолютного Духа исчезнут сомнения он придёт к Абсолютной Идее Себя а история закончится и настанет Царство Свободы. Войны между народами выражают напряжённое столкновение мыслей Абсолютного Духа.
31442. Мир, природа, бытие, субстанция, материя 25.5 KB
  Философском энциклопедическом словаре имеется следующее определение: âБытие философская категория обозначающая реальность существующую объективно вне и независимо от сознания человекаâ. Самый первый философ кот изучал бытие Парменид: бытие есть не бытие нет мыслимое существует не мыслимое не существует. У Платона бытиеэто мир идей.
31443. Материя и проблема субстанции в философии. Монизм, дуализм, плюрализм. Философия и наука о материальном единстве мира как единстве многообразия сущего 36.5 KB
  Материя как субстанция обладает свойствами: несотворимость неуничтожимость бесконечность способность к саморазвитию. Материя как субстанция не существует отдельно от материальных явлений как нечто самостоятельное она существует только в них и через них. Материя объективное бытие.
31444. Материя и движение. Движение – способ существования материи. Диалектика абсолютного и относительного движения. Движение и покой 28.5 KB
  Диалектика абсолютного и относительного движения. В онтологическом смысле материя это бесконечное множество всех существующих в мире объектов и систем субстрат любых свойств связей отношений и форм движения; в мире нет ничего кроме движущейся материи . Относительность: нет просто движения движения вообще а есть только его отдельные формы ограничение его исторически и локально в пространстве. Прекращение одних форм движения замещается возникновением др.