13.12.2013БИК Специальность ПОВТ Дисциплина Численные методы 1. - презентация

1 БИК Специальность ПОВТ Дисциплина Численные методы 1

2 БИК Специальность ПОВТ Дисциплина Численные методы 2 В общем виде система m линейных алгебраических уравнений с n неизвестными: a 11 x 1 + a 12 x 2 + … + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n = b 2 a m1 x 1 + a m2 x 2 + … + a mn x n = b m … 1. Определения, обозначения, общие сведения

3 БИК Специальность ПОВТ Дисциплина Численные методы 3 Обозначим: a 11 a 12 … a 1n a 21 a 22 … a 2n … a n1 a n2 … a nn A = x1x2…xnx1x2…xn X = b1b2…bnb1b2…bn B = матрица коэффициентов столбец свободных членов столбец неизвестных Тогда в матричном виде можно записать AX = B

4 БИК Специальность ПОВТ Дисциплина Численные методы 4 Решением системы (1) называется такая упорядоченная совокупность чисел …,, которая обращает все уравнения системы в верные равенства

5 БИК Специальность ПОВТ Дисциплина Численные методы 5

6 БИК Специальность ПОВТ Дисциплина Численные методы 6 Транспонированная матрица

7 БИК Специальность ПОВТ Дисциплина Численные методы 7 Итерационные Численные методы решения СЛАУ Прямые (точные) Метод Крамера Метод Гаусса Метод ортогонализации Метод простой итерации Метод Зейделя Метод релаксаций Градиентные методы

8 БИК Специальность ПОВТ Дисциплина Численные методы 8 Шаг 1 Получение расширенной матрицы - добавим к основной матрице A столбец свободных членов B a 11 a 12 … a 1n a 21 a 22 … a 2n … a n1 a n2 … a nn A = b1b2…bnb1b2…bn Фрагмент блок-схемы 3. Метод Гаусса (метод последовательного исключения неизвестных)

9 БИК Специальность ПОВТ Дисциплина Численные методы 9 Шаг 2 Прямой ход метода Гаусса - приведение расширенной матрицы к треугольному виду a 11 a 12 a 13 … a 1n-1 a 1n 0 a 22 a 23 … a 2n-1 a 2n 0 0 a 33 … a 3n-1 a 3n … … 0 a nn A = b1b2b3…bnb1b2b3…bn Как это сделать?

10 БИК Специальность ПОВТ Дисциплина Численные методы 10 а. Формирование первого столбца матрицы a 11 a 12 … a 1n b 1 a 21 a 22 … a 2n b 2 a n1 a n2 … a nn b n … a 31 a 32 … a 3n b 3 M = a 11 a 21 a 11 a 12 … a 1n b1b1 a 22 … a 2n b2b2 a n2 … a nn bnbn … a 32 … a 3n b3b3 a 21 :=a 21 -M. a 11 =0; a 22 :=a 22 -M. a 12 ; … M = a 11 a 31 a 31 :=a 31 -M. a 11 =0; a 32 :=a 32 -M. a 12 ; … M = a 11 a n1 a n1 :=a n1 -M. a 11 =0; a n2 :=a n2 -M. a 12 ; … б. Формирование второго столбца матрицы a 11 a 12 … a 1n b 1 0 a 22 … a 2n b 2 0 a n2 … a nn b n … 0 a 32 … a 3n b 3 a 11 a 12 … a 1n b1b1 0 a 22 … a 2n b2b2 … a nn bnbn … … a 3n b3b3 M = a 22 a 32 a 32 :=a 32 -M. a 22 =0; a 33 :=a 33 -M. a 23 ; … M = a 22 an2an2 a n2 :=a n2 -M. a 22 =0; a n3 :=a n3 -M. a 23 ; … И т.д. до n-го столбца: a ij: := a ij – M. a kj M = a kk a ik ; Но возникает вопрос …

11 БИК Специальность ПОВТ Дисциплина Численные методы 11 Если на главной диагонали встретится нулевой элемент, то рассчитать коэффициент M будет невозможно (делить на ноль нельзя) Перед обнулением элементов в k-том столбце среди элементов, лежащих ниже диагонального, найти максимальный по модулю, запомнить номер строки, в котором он находится, и поменять эту строку с k-той строкой местами. Например, a 11 a 12 … a 1n b … a 2n b 2 0 a n2 … a nn b n … 0 a 32 … a 3n b 3 Допустим, среди элементов а 32 …а n2 максимальным является элемент 3-ей строки а 32 a 11 a 12 … a 1n b1b1 0 a 22 … a 2n b2b2 0 a n2 … a nn bnbn … 0 0 … a 3n b3b3 Фрагмент блок-схемы

12 БИК Специальность ПОВТ Дисциплина Численные методы 12 Шаг 3 Обратный ход метода Гаусса -нахождение неизвестных После преобразований система уравнений имеет вид: a 11 x 1 + … + a 1 n-2 x n-2 + a 1 n-1 x n-1 + a 1 n xn xn = b1b1 a n-2n-2 x n-2 + a n-2n-1 x n-1 + a n-2n x n = b n-2 a n-1n-1 x n-1 + a n-1n x n = b n-1 a nn x n = bnbn … Из последнего уравнения: Если a nn = 0, то x n = bnbn a nn ; если a nn = 0 и bn bn = 0, то если a nn = 0 и b n = 0, то x n-1 = b n-1 - a n-1n. x n a n-1n-1 ; x n-2 = b n-2 - a n-2n-1. x n-1 - a n-2n. x n a n-2n-2 ; … x i = b i - a ij. x j a ii Фрагмент блок-схемы система имеет бесконечное множество решений; система решений не имеет.

13 БИК Специальность ПОВТ Дисциплина Численные методы 13 начало n i:=1,n j:=1,n a ij bibi Вернуться к описанию вводим размерность матрицы открываем внешний цикл по номеру строки открываем внутренний цикл по номеру столбца вводим значение элемента строки в качестве последнего элемента каждой строки вводим значение свободного члена

14 БИК Специальность ПОВТ Дисциплина Численные методы 14 если модуль текущего элемента больше max, то начало n i:=1,n j:=1,n a ij bibi k:=1,n max:=|a kk | r:=k i:=k+1,n |a ik |>max max:=|a ik | r:=i j:=1,n c:=a kj a kj :=a rj a rj :=c открываем цикл по номеру столбца сохраняем в max модуль диагонального элемента текущей строки; в r запоминаем номер текущей строки внутренний цикл по номеру строки для просмотра элементов, лежащих ниже диагонального сохраняем его значение в max, а в r запоминаем номер текущей строки открываем цикл по номеру столбца меняем местами элементы текущей строки и строки, содержащей максимальный элемент a ij := a ij – M. a kj M = a kk a ik ;

15 БИК Специальность ПОВТ Дисциплина Численные методы 15 начало n i:=1,n j:=1,n a ij bibi Вернуться к описанию c:=b k b k :=b r b r :=c i:=k+1,n M:=a ik /a kk j:=1,n a ij :=a ij - Ma kj b i :=b i - Mb k если модуль текущего элемента больше max, то k:=1,n max:=|a kk | r:=k i:=k+1,n |a ik |>max max:=|a ik | r:=i j:=1,n c:=a kj a kj :=a rj a rj :=c открываем цикл по номеру столбца сохраняем в max модуль диагонального элемента текущей строки; в r запоминаем номер текущей строки внутренний цикл по номеру строки для просмотра элементов, лежащих ниже диагонального сохраняем его значение в max, а в r запоминаем номер текущей строки открываем цикл по номеру столбца меняем местами элементы текущей строки и строки, содержащей максимальный элемент открываем цикл по номерам строк, лежащих ниже диагонали находим коэффициент для текущей строки в цикле по номеру строки присваиваем элементам строки новые значения последним элементом строки является новое значение свободного члена a ij := a ij – M. a kj M = a kk a ik ;

16 БИК Специальность ПОВТ Дисциплина Численные методы 16 начало n i:=1,n j:=1,n a ij bibi c:=b k b k :=b r b r :=c i:=k+1,n M:=a ik /a kk j:=1,n a ij :=a ij - Ma kj b i :=b i - Mb k k:=1,n max:=|a kk | r:=k i:=k+1,n |a ik |>max max:=|a ik | r:=i j:=1,n c:=a kj a kj :=a rj a rj :=c a nn =0 i:=n,1, -1 s:=0 j:=i+1, n s:=s + a ij x j x i :=(b i – s)/a ii xixi b n =0 конец Бесконечное мн-во решений Нет решений - + если последний элемент диагонали равен 0, то… если последний свободный член равен 0, то… иначе… иначе открываем обратный цикл по номеру строки обнуляем сумму цикл по номерам столбцов, лежащих правее диагонального элемента (для последней строки не выполняется) накапливаем сумму находим неизвестное в текущей строке выводим текущее неизвестное - 23 x i = b i - a ij. x j a ii

17 БИК Специальность ПОВТ Дисциплина Численные методы 17 начало n i:=1,n j:=1,n a ij bibi k:=1,n max:=|a kk | r:=k i:=k+1,n |a ik |>max max:=|a ik | r:=i j:=1,n c:=a kj a kj :=a rj a rj :=c c:=b k b k :=b r b r :=c i:=k+1,n M:=a ik /a kk j:=1,n a ij :=a ij - Ma kj b i :=b i - Mb k a nn =0 i:=n,1, -1 s:=0 j:=i+1, n s:=s + a ij x j x i :=(b i – s)/a ii xixi b n =0 Бесконечное мн-во решений Нет решений конец