Методы решения систем линейных уравнений

Лабораторная работа №3

по курсу:

«Высокопроизводительные вычислительные системы»

Решение систем линейных уравнений.

Содержание:

«Высокопроизводительные вычислительные системы»................................................................... 1

1. Введение...................................................................................................................................................................................... 1

Цель лабораторной работы................................................................................................................................................... 1

Основные характеристики лабораторной работы......................................................................................................... 1

2. Методические указания к лабораторной работе................................................................................. 2

Методы решения систем линейных уравнений............................................................................................................ 2

Метод исключения (метод Гаусса)........................................................................................................................................ 2

Итерационный метод Гаусса-Зейделя................................................................................................................................. 5

Итерационный метод Якоби.................................................................................................................................................. 6

Блочный метод............................................................................................................................................................................ 7

Алгоритм выделения ветвей независимых операций в последовательной программе для её распараллеливания............................................................................................................................................................................................................... 8

Критерий выделения параллельных ветвей для машин класса МКМД (MIMD)........................................................ 8

3. Задание....................................................................................................................................................................................... 10

Домашняя подготовка............................................................................................................................................................ 10

Задание в лаборатории.......................................................................................................................................................... 10

4. Литература.............................................................................................................................................................................. 11

Приложение 1. Варианты задания.......................................................................................................................... 11

Приложение 2. Содержание отчёта о выполнении лабораторной работы..................... 11

Приложение 3. Основные функции библиотеки MPI............................................................................. 11

Введение.

Цель лабораторной работы

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

Основные характеристики лабораторной работы

В ходе выполнения ЛР, студенты знакомятся с одним из численных методов решения системы линейных уравнений. Дальнейшая работа предусматривает выполнение нескольких этапов подготовки параллельной программы. Сюда входят: 1) Отладка последовательного алгоритма указанного в задании численного метода; 2) Выявление независимых операций и создание параллельного алгоритма этого метода; 3) Написание параллельной программы с использованием библиотеки MPI реализующий данный алгоритм; 4) Подготовка тестовой задачи. Далее, в ходе лабораторной работы, происходит отладка и выполнение программы на кластерной параллельной ВС.

Методические указания к лабораторной работе.

Методы решения систем линейных уравнений

Метод исключения (метод Гаусса)

Метод исключения или метод Гаусса является одним из наиболее часто применяемых прямых (не итерационных) методов решения систем линейных уравнений.

Чтобы проиллюстрировать этот метод, рассмотрим сначала систему из трёх уравнений с тремя неизвестными:

{

a11x1+a12x2+a13x3 a21x1+a22x2+a23x3 a31x1+a32x2+a33x3

=b1, =b2, =b3.

(3.1) (3.2) (3.3)

В такой системе по крайней мере один из коэффициентов a₁₁,a₂₂,a₃₃ должен быть отличен от нуля, иначе мы имели бы дело в этих трёх уравнениях только с двумя неизвестными. Если a₁₁=0, то можно переставить уравнения так, чтобы коэффициент при x₁ в первом уравнении был отличен от нуля. Очевидно, что перестановка уравнений оставляет систему неизменной: её решение остаётся прежним.

Теперь введём множитель

m₂=a₂₁/a₁₁.

Умножим первое уравнение системы (3.1) на m₂ и вычтем его из уравнения (3.2). (“Первое” и “второе” уравнения мы берём уже после перестановки, если она была необходима.) Результат вычитания равен:

(a₂₁ - m₂a₁₁)x₁+(a₂₂ - m₂a₁₂)x₂+(a₂₃ - m₂a₁₃)x₃=b₂ - m₂b₁. (3.4)

Но ведь при этом

a₂₁ - m₂a₁₁= a₂₁ – (a₂₁/a₁₁)a₁₁=0,

так что x₁ исключено из второго уравнения (конечно именно для достижения такого результата и было выбрано значение m₂). Определим теперь новые коэффициенты

a’22 a’23 b’2

=a22 - m2a12, =a23 - m2a13, =b2 - m2b1.

Тогда уравнение (3.2) приобретает вид

a’22x2+ a’23x3

= b’2.

(3.5)

Заменим второе из первоначальных уравнений (3.2) уравнением (3.5) и введём множитель для третьего уравнения

m₃=a₃₁/a₁₁.

Умножим первое уравнение на это множитель и вычтем его из третьего. Коэффициент при x₁ снова становится нулевым, и третье уравнение приобретает вид

a’32x2+ a’33x3

= b’3.

(3.6)

Где

a’32 a’33 b’3

=a32 – m3a12, =a33 – m3a13, =b3 – m3b1.

Если теперь в исходной системе уравнений заменить (3.3) на (3.6), то новая система выглядит так:

{

a11x1+a12x2+a13x3 a’22x2+ a’23x3 a’32x2+ a’33x3

=b1, =b’2, =b’3.

(3.1) (3.5) (3.6)

Полученная система уравнений ((3.1)(3.5)(3.6)) полностью эквивалентна исходной системе уравнений ((3.1)(3.2)(3.3)). Нетрудно заметить, что проведённые нами действия позволили исключить из второго и третьего уравнений системы член с переменной x₁. Таким образом, два последних уравнения представляют собой систему из двух уравнений с двумя неизвестными; если теперь найти решение этой системы, т.е. определить x₂ и x₃, то результат можно подставить в первое уравнение и найти x₁.

Попытаемся теперь исключить x₂ из двух последних уравнений. Если a’₂₂=0, то снова мы переставим уравнения так, чтобы a’₂₂ было отлично от нуля. (Если же a’₂₂=0 и a’₃₂=0, то система вырождена и либо вовсе не имеет решения, либо имеет бесчисленное множество решений.)

Введём новый множитель

m’₃=a’₃₂/a’₂₂.

Умножим уравнение (3.5) на m’₃ и вычтем его из (3.6). Результат вычитания равен

(a’₃₂ – m’₃a’₂₂)x₂+(a’₃₃ – m’₃a’₂₃)x₃=b’₃ – m’₃b’₂.

В силу выбора m’₃

a’₃₂ – a’₃a’₂₂=0.

Полагая

a”33 b”3

=a’33 – m’3a’23, =b’3 – m’3b’2.

окончательно получаем

a”33x3

=b”3.

(3.7)

Уравнение (3.6) можно заменить уравнением (3.7), после чего система уравнений приобретает следующий вид:

{

a11x1+a12x2+a13x3 a’22x2+ a’23x3 a”33x3

=b1, =b’2, =b”3.

(3.1) (3.5) (3.7)

Такая система уравнений иногда называется треугольной из-за своего внешнего вида.

Теперь, для решения системы уравнений надо определить x₃ из (3.7), подставить этот результат в (3.5), определить x₂ из (3.5), подставить x₂ и x₃ в (3.1) и определить x₁. Этот процесс, который обычно называется обратной подстановкой, определяется в нашем случае формулами

x3 x2 x1

= b”3/a”33, = (b’2 - a’23x3)/ a’22, = (b1 - a12x2 - a13x3)/ a11.

Таким образом решается система состоящая из трёх линейных уравнений.

Теперь рассмотрим общий случай, когда имеется система из n уравнений с n неизвестными. Обозначим неизвестные через x₁, x₂, …, x_n и запишем систему уравнений в следующем виде:

{

a11x1+a12x2+…+a1nxn a21x1+a22x2+…+a2nxn …………………………………. an1x1+an2x2+…+annxn

=b1, =b2, …. =bn.

(3.8)

Для системы из n уравнений мы должны будем провести n-1 этапов исключения. На каком-то k –м этапе исключения m, a и b подсчитываются по следующим формулам:

m(k-1)i= a(k)ij= b(k)i=

a(k-1)ik/a(k-1)kk, a(k-1)ij - m(k-1)ia(k-1)kj, b(k-1)i – m(k-1)ib(k-1)k.

i=k+1,…,n, j=k,…,n.

- где верхний индекс у каждого параметра означает номер этапа, на котором этот параметр подсчитывается.

Необходимо четко представлять себе смысл индексов i, j, и k.

k означает номер того уравнения, которое вычитается из остальных, а так же номер того неизвестного, которое исключается из оставшихся n-k уравнений.

i означает номер уравнения, из которого в данный момент исключается неизвестное.

j означает номер столбца.

При k=n-1 происходит исключение x_n-1 из последнего уравнения.

Окончательная треугольная система уравнений записывается следующим образом:

{

a11x1+a12x2+…+a1nxn a’22x2+…+a’2nxn …………………………………. an-1nnxn

=b1, =b’2, …. =bn-1n.

(3.9)

Обратная подстановка для нахождения значений неизвестных задаётся формулами:

xn= xn-1= …… xj=

b(n-1)n/a(n-1)nn, (b(n-2)n-1 - a(n-2)n-1,nxn)/ a(n-2)n-1,n-1, ………………………….. (b(j-1)j - a(j-1)j,nxn- …- a(j-1)j,j+1xj+1 /a(j-1)j,j.

Для j=n-2,n-3,…,1.

Итерационный метод Гаусса-Зейделя

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

Предположим, что у нас есть система, состоящая из трёх линейных уравнений с тремя неизвестными.

{

a11x1+a12x2+a13x3 a21x1+a22x2+a23x3 a31x1+a32x2+a33x3

=b1, =b2, =b3.

Предположим a₁₁¹0, a₂₂¹0, a₃₃¹0, и перепишем систему в следующем виде:

x1= x2= x3=

(b1-a12x2-a13x3)/a11, (b2-a21x1-a23x3)/a22, (b3-a31x1-a32x2)/a33.

(3.10) (3.11) (3.12)

Теперь возьмём некоторое первое приближение к решению этой системы, обозначив его через x⁰₁, x⁰₂, x⁰₃. Подставим это решение в (3.10) и вычислим новое значение x₁:

x⁽¹⁾₁=(b₁-a₁₂x⁰₂-a₁₃x⁰₃)/a₁₁.

Используя только что вычисленное значение x⁽¹⁾₁ и начальное значение x⁰₃, вмчислим из уравнения (3.11) новое значение x₂:

x⁽¹⁾₂=(b₂-a₂₁x¹₁-a₂₃x⁰₃)/a₂₂.

Наконец, используя только что вычисленные значения x⁽¹⁾₁ и x⁽¹⁾₂, найдём из (3.12) новое значение x₃:

x⁽¹⁾₃=(b₃-a₃₁x¹₁-a₃₂x¹₂)/a₃₃.

Этим заканчивается первая итерация. Теперь можно заменить исходные значения x⁰₁, x⁰₂, и x⁰₃ на x⁽¹⁾₁, x⁽¹⁾₂, x⁽¹⁾₃ и вычислить следующее приближение. В общем случае k-е приближение определяется формулами

{

x(k)1= x(k)2= x(k)3=

(b1-a12x(k-1)2-a13x(k-1)3)/a11, (b2-a21x(k)1-a23x(k-1)3)/a22, (b3-a31x(k)1-a32x(k)2)/a33.

(3.13)

Заметим, что текущие значения неизвестных сразу же используются для последующих вычислений и что, например, нельзя вычислять x^(k)₂, пока не получено x^(k)₁. Аналогично этому для вычисления x^(k)₃ необходимо сначала определить x^(k)₁ и x^(k)₂.

Рассмотрим теперь систему (3.14) с n уравнениями и n неизвестными.

{

a11x1+a12x2+…+a1nxn a21x1+a22x2+…+a2nxn …………………………………. an1x1+an2x2+…+annxn

=b1, =b2, …. =bn.

(3.14)

Мы по прежнему полагаем, что диагональные коэффициенты a_ij отличны от нуля для всех i. Тогда k-е приближение к решению будет задаватся формулой

x^(k)_i=(b_i-a_i1x^(k)₁-…-a_i,i-1x^(k)_i-1 - a_i,i+1x^(k-1)_i+1-…-a_inx^(k-1)_n)/a_ii, i=1,2,…,n.

Итерационный процесс продолжается до тех пор, пока все x^(k)_i не станут достаточно близки к x^(k-1)_i. Критерий близости можно, например, задать в следующем виде:

M^(k)=max| x^(k)_i - x^(k-1)_i |<e,

где определяется максимальное значение разности для всех i, а e -некоторое положительное число. При выполнении критерия итерационный процесс следует остановить. Можно заменить этот критерий близости, сравнивая с e не абсолютные, а относительные разности

max|(x^(k)_i - x^(k-1)_i)/ x^(k)_i|<e,

Итерационный метод Якоби

Метод Якоби - метод, в котором решение получается путём постепенного итерационного (пошагового) приближения к нему и уточнения результата.

Предположим, что у нас есть система, состоящая из трёх линейных уравнений с тремя неизвестными.

{

a11x1+a12x2+a13x3 a21x1+a22x2+a23x3 a31x1+a32x2+a33x3

=b1, =b2, =b3.

(3.15)

Предположим a₁₁¹0, a₂₂¹0, a₃₃¹0, и перепишем систему в следующем виде:

x1= x2= x3=

(b1-a12x2-a13x3)/a11, (b2-a21x1-a23x3)/a22, (b3-a31x1-a32x2)/a33.

(3.16) (3.17) (3.18)

Теперь возьмём некоторое первое приближение к решению этой системы, обозначив его через x⁰₁, x⁰₂, x⁰₃. Подставим это решение в (3.16, 3.17,3.18) и вычислим новые значения x_1,, x₂, x₃:

x⁽¹⁾₁=(b₁-a₁₂x⁰₂-a₁₃x⁰₃)/a_11;

x⁽¹⁾₂=(b₂-a₂₁x⁰₁-a₂₃x⁰₃)/a_22;

x⁽¹⁾₃=(b₃-a₃₁x⁰₁-a₃₂x⁰₂)/a₃₃.

Этим заканчивается первая итерация.

Теперь можно заменить исходные значения x⁰₁, x⁰₂, и x⁰₃ на x⁽¹⁾₁, x⁽¹⁾₂, x⁽¹⁾₃ и вычислить следующее приближение.

В общем случае k-е приближение определяется формулами

{

x(k)1= x(k)2= x(k)3=

(b1-a12x(k-1)2-a13x(k-1)3)/a11, (b2-a21x(k-1)1-a23x(k-1)3)/a22, (b3-a31x(k-1)1-a32x(k-1)2)/a33.

(3.19)

Заметим, что текущие значения неизвестных не сразу используются для последующих вычислений и что, например, нельзя вычислять x^(k)_i, пока не получены все x^(k-1).

Рассмотрим теперь систему (3.20) с n уравнениями и n неизвестными.

{

a11x1+a12x2+…+a1nxn a21x1+a22x2+…+a2nxn …………………………………. an1x1+an2x2+…+annxn

=b1, =b2, …. =bn.

(3.20)

Мы по прежнему полагаем, что диагональные коэффициенты a_ij отличны от нуля для всех i. Тогда k-е приближение к решению будет задаваться формулой

x^(k)_i=(b_i-a_i1x^(k-1)₁-…-a_i,i-1x^(k-1)_i-1 - a_i,i+1x^(k-1)_i+1-…-a_inx^(k-1)_n)/a_ii, i=1,2,…,n.

Итерационный процесс продолжается до тех пор, пока все x^(k)_i не станут достаточно близки к x^(k-1)_i. Критерий близости можно, например задать в следующем виде:

M^(k)=max| x^(k)_i - x^(k-1)_i |<e,

где определяется максимальное значение разности для всех i, а e -некоторое положительное число. При выполнении критерия итерационный процесс следует остановить. Можно заменить этот критерий близости, сравнивая с e не абсолютные, а относительные разности

max|(x^(k)_i - x^(k-1)_i)/ x^(k)_i|<e,

Блочный метод