Численное решение системы линейных уравнений с помощью метода исключения Гаусса с выбором главного элемента по столбцу

СОДЕРЖАНИЕ

Введение

1 Постановка задачи

2 Математические и алгоритмические основы решения задачи

2.1 Схема единственного деления

2.1.1 Прямой ход

2.1.2 Обратный ход

2.2 Метод Гаусса с выбором главного элемента по столбцу

3 Функциональные модели и блок-схемы решения задачи

4 Программная реализация решения задачи

5 Пример выполнения программы

Заключение

Список использованных источников и литературы

ВВЕДЕНИЕ

Решение систем линейных алгебраических уравнений – одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности – нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма.

Одна из трудностей практического решения систем большой размерности связанна с ограниченностью оперативной памяти ЭВМ. Хотя объем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее, еще быстрее возрастают потребности практики в решении задач все большей размерности. В значительной степени ограничения на размерность решаемых систем можно снять, если использовать для хранения матрицы внешние запоминающие устройства. Однако в этом случае многократно возрастают как затраты машинного времени, так и сложность соответствующих алгоритмов. Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ.

К счастью, приложения очень часто приводят к матрицам, в которых число ненулевых элементов много меньше общего числа элементов матрицы. Такие матрицы принято называть разреженными. Одним из основных источников разреженных матриц являются математические модели технических устройств, состоящих из большого числа элементов, связи между которыми локальны. Простейшие примеры таких устройств – сложные строительные конструкции и большие электрические цепи.

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

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

Вычисления с помощью метода Гаусса заключаются в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с верхней треугольной матрицей. Вычисления значений неизвестных производят на этапе обратного хода.

Целью данной курсовой работы является численное решение системы линейных уравнений с помощью метода исключения Гаусса с выбором главного элемента по столбцу.

1 Постановка задачи

Задача ставится следующим образом. Пусть требуется найти решение системы линейных алгебраических уравнений

a_1,1x₁ + a_1,2x₂ + a_1,3x₃ + . . . + a_1,nx_n = b₁

a_2,1x₁ + a_2,2x₂ + a_2,3x₃ + . . . + a_2,nx_n = b₂

 (1)

a_n,1x₁ + a_n,2x₂ + a_n,3x₃ + . . . + a_n,nxn = b_n

или в векторной форме

AX=B

где A -матрица коэффициентов; X - вектор неизвестных; B- вектор правых частей.

Будем считать, что D = det A ¹ 0 т.е. решение существует и единственно.

Рассмотрим вначале прямые методы. В явном виде решение системы (1) записывается в виде формул Крамера

x_i = D _i/D

где D _i - определитель матрицы, которая получается из матрицы A путем замены i-того столбца на столбец правых частей.

Этот метод очень неэкономичен так как для его применения требуется (n+1)! операций, поэтому на практике используются различные варианты метода исключения переменных (Гаусса). Метод исключения переменных состоит из двух этапов: прямого хода, заключающегося в преобразовании исходной системы к системе с треугольной матрицей коэффициентов, и обратного хода, т.е. решения системы с треугольной матрицей.

Пример 1. Решить следующую систему с помощью метода исключения Гаусса с выбором главного элемента по столбцу:

_.

Решение:

_.

Пример 2. Решить следующую систему с помощью метода исключения Гаусса с выбором главного элемента по столбцу:

_.

Составим расширенную матрицу системы.

 

.

 

Решением системы являются:x =1, y = 2, z = 3.

2 Математические и алгоритмические основы решения задачи

2.1 Схема единственного деления

Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления.

2.1.1 Прямой ход

Прямой ход состоит из n - 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a11 = 0. Будем называть его главным элементом 1-го шага.

Найдем величины

qi1 = ai1/a11 (i = 2, 3, …, n),

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31, qn1. Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a11x1 + a12x2 + a13x3 + … + a1nxn = b1 ,

a22(1)x2 + a23(1)x3 + … + a2n(1)xn = b2(1) ,

a32(1)x2 + a33(1)x3 + … + a3n(1)xn = b3(1) ,

an2(1)x2 + an3(1)x3 + … + ann(1)xn = bn(1) .

в которой aij(1) и bij(1) вычисляются по формулам

aij(1) = aij − qi1a1j bi(1) = bi − qi1b1.

2-й шаг. Целью этого шага является исключение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22(1) ≠ 0, где a22(1) – коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

qi2 = ai2(1) / a22(1) (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2.

В результате получим систему

a11x1 + a12x2 + a13x3 + a1nxn =b1,

a22(1)x2 + a23(1)x3 + a2n(1) =b2(1) ,

a33(2)x3 + a3n(2)xn =b3(2),

an3(2)x3 + ann(2)xn = bn(2)

Здесь коэффициенты aij(2) и bij(2) вычисляются по формулам

aij(2) = aij(1) – qi2a2j(1) ,bi(2) = bi(1) – qi2b2(1).

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k-й шаг. В предположении, что главный (ведущий) элемент k-го шага akk(k–1) отличен от нуля, вычислим множители k-го шага

qik = aik(k–1) / akk(k–1) (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на

qk+1,k, qk+2,k, …, qnk.

После (n - 1)-го шага исключения получим систему уравнений

a11x1 +a12x2 +a13x3 + a1nxn= b1

a22(1)x2 a23(1)x3 +… + a2n(1)xn = b2(1)

a33(2)x3 + a3n(2)xn = b3(2),

ann(n–1)xn =bn(n–1)

Матрица A(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.