40830

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

Лекция

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

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

Русский

2013-10-22

1 MB

97 чел.

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


 

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

73953. Геодезические работы в строительстве 2.45 MB
  Геодезические работы в строительстве. Организация геодезических работ в строительстве Геодезическая основа строительства Перенос на местность здания или сооружения. Организация геодезических работ в строительстве Виды геодезических работ в строительстве. На строительномонтажной площадке выполняются следующие геодезические работы.
73954. ЭЛЕМЕНТЫ ГЕОДЕЗИЧЕСКИХ РАЗБИВОЧНЫХ РАБОТ 1.29 MB
  Перенесение на местность проектных расстояний Построение проектного угла Вынесение на местность проектных отметок Построение линии с проектным углом I вопрос. Построение линии проектной длины А С обычной технической точностью когда относительные погрешности...
73955. Геодезические работы при детальной разбивке закруглений и закрепление на местности осей сооружения 2.23 MB
  Закрепление на местности осей здания или сооружения. Выбор вида закрепления осей на местности определяется характеристикой объекта строительства и классом его точности. Закрепление осей обноской Обноска – специальное приспособление ограждение применяемое на строительной площадке при выносе осей сооружения и их закрепления.
73956. Геодезические работы при строительстве зданий, сооружений 1.43 MB
  Геодезические работы при сооружении котлованов Задача геодезиста: Разметка планового контура котлована плановая разбивка; Контроль глубины отрывки котлована высотная разбивка; Исходные документы: разбивочный чертёж как вариант; план топографической съёмки масштаба
73957. Топографический план (карта) и решаемые по ним задачи 1.79 MB
  Системы координат в инженерной геодезии. В России топографические планы и карты строят в ортогональной равноугольной поперечно-цилиндрической проекции и соответствующей ей системе плоских прямоугольных координат Гаусса Крюгера Г К. Топографические съемки в крупных масштабах на участках площадью менее 20 км2 выполняются как правило в частных системах прямоугольных координат. Разграфка листов планов в этих случаях производится не меридианами и параллелями а линиями координатной сетки.
73958. Угловые измерения 1.26 MB
  Классификация теодолитов и особенности устройства ЭОП теодолитов-тахеометров Измерение горизонтальных и вертикальных углов. Принцип измерения горизонтальных и вертикальных углов Угловые измерения занимают составляют основу геодезических измерений на местности. Измерения вертикальных углов.
73960. Геодезическая опорная сеть 824 KB
  Совокупность этих пунктов составляет опорную геодезическую сеть.1 Назначение государственной геодезической сети Государственная геодезическая сеть далее ГГС представляет собой совокупность геодезических пунктов расположенных равномерно по всей территории и закрепленных на местности специальными центрами обеспечивающими их сохранность и устойчивость в плане и по высоте в течение длительного времени. Координаты ее пунктов определены по доплеровским фотографическим дальномерным радиотехническим и лазерным наблюдениям искусственных...
73961. Поверки и юстировки теодолита 1.05 MB
  Каждый теодолит должен отвечать определенным оптико-механическим и геометрическим условиям, вытекающим из схемы измерения горизонтальных и вертикальных углов.