Меню Закрыть

Схема частичного выбора метода гаусса

1. На первом шаге прямого хода метода Гаусса выбирается максимальный по модулю элемент в первом столбце. Этот элемент является ведущим. Если он равен нулю, то detA = 0. Если ведущий элемент не является элементом , то перестановкой строк помещаем его в . При этом соответственно переставляются элементы вектора b. Затем применяются формулы метода Гаусса.

2. На -м шаге прямого хода метода Гаусса непреобразованный столбец – это часть столбца i, начиная с элемента , то есть . Находим максимальный по модулю элемент в непреобразованном столбце. Этот элемент является ведущим. Если он равен нулю, то detA = 0. Если ведущий элемент не является элементом , то перестановкой строк помещаем его в . При этом соответственно переставляются элементы вектора b. Затем применяются формулы метода Гаусса.

3. После (n-1)-го шага получаем верхнюю треугольную матрицу U и преобразованный вектор правой части. Выполняем обратную подстановку.

Метод Гаусса с частичным выбором ведущего элемента в отсутствие ошибок округления для невырожденных матриц позволяет получить точное решение, а для вырожденных матриц – сообщение о том, что матрица вырождена.

Решить систему линейных уравнений методом Гаусса с частичным выбором ведущего элемента.

Рассмотрим ту же систему линейных уравнений, что и в предыдущих примерах.

Прямой ход метода Гаусса

Прежде всего, выбираем максимальный по модулю элемент в первом непреобразованном столбце:

, , следовательно, ведущим элементом является 10.

Ведущим элементом является элемент , поэтому перестановка строк не нужна. Умножим первое уравнение на 0.3 и прибавим ко второму. Умножим первое уравнение на -0.5 и прибавим к третьему. Получим:

Рассмотрим следующий непреобразованный столбец:

, , следовательно, ведущим элементом является 2.5, а не -0.1, как в методе Гаусса без выбора ведущего элемента. Но ведущий элемент не является элементом ( при ) , поэтому необходимо переставить строки матрицы А, чтобы элемент 2.5 стал элементом .

Умножим второе уравнение на 0.4 и прибавим к третьему. Получим:

Мы получили систему линейных уравнений с верхней треугольной матрицей.

Ведущими элементами являются числа: 10, 2.5, 6.2, все они по модулю больше 1, следовательно, алгоритм является вычислительно устойчивым.

Читайте также:  Intel iris graphics 6000

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

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

Произвольная невырожденная матрица перестановкой строк (столбцов) может быть приведена к матрице с главными минорами, отличными от нуля ( , где P – матрица перестановок).

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

Сложность метода Гаусса с частичным выбором ведущего элемента

Число арифметических действий, необходимых для его реализации: , где n – число уравнений. Оценим сложность по памяти: требуется память для хранения n 2 элементов матрицы, вектора b (n элементов) и вектора x (n элементов), в результате, .

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

Следует отметить, что метод Гаусса с частичным выбором ведущего элемента – это основной алгоритм вычислительной математики линейной алгебры.

Метод Гаусса с полным выбором ведущего элемента отличается от метода Гаусса с частичным выбором ведущего элемента тем, что на каждом шаге прямого хода ведущий элемент ищется в непреобразованной части матрицы. Непреобразованная часть матрицы – это квадратная матрица размерности n-i+1, получаемая вычеркиванием первых i – 1 строк и первых i – 1 столбцов. В методе Гаусса с полным выбором ведущего элемента возможна не только перестановка строк матрицы и соответствующих элементов правой части, но и перестановка столбцов матрицы и, соответственно, изменение порядка следования неизвестных.

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

На k-ом шаге прямого хода в качестве ведущего элемента выбирают максимальный по модулю коэффициент при неизвестной в уравнениях с номерами i = k+1, . , m.Затем уравнение, соответствующее выбранному коэффициенту с номером , меняют местами с к-ым уравнением системы для того, чтобы главный элемент занял место коэффициента . После этой перестановки исключение проводят как в схеме единственного деления. В этом случае все масштабирующие множители по модулю меньше единицы и схема обладает вычислительной устойчивостью.

Читайте также:  Lg v10 dual sim

ПРИМЕР 1.Решение системы методом Гаусса с выбором главного элемента по столбцу.

A= , b= .

Прямой ход. 1 шаг. Максимальный по модулю элемент 1-го столбца . Переставим 1-ое и 3 – е уравнения местами:

A= , b= .

Вычислим масштабирующие множители 1 шага:

и выполним преобразование матрицы и вектора:

A1= b1= .

2 шаг. Вычислим масштабирующие множители 2 шага:

.

Второй шаг не изменяет матриц: A2=A1, b2= b1.

3 шаг. Максимальный по модулю элемент 3 столбца . Переставим 3 и 4 уравнения местами.

A2= b2= .

Вычислим масштабирующие множители 3 шага:

и выполним преобразование матрицы и вектора:

A3= b3= .

Обратный ход. Из последнего уравнения находим: . Из третьего

уравнения системы находим . Из второго уравнения находим

. Неизвестное находим из первого уравнения:

Ответ: .

% Решить систему Ax=b методом Гаусса

% Введём правую часть

b = [-14; 44; 142; -76];

% Решим систему средствами MATLAB

x =-8.0000
-2.0000
-2.0000
-0.0000

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9526 – | 7348 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

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

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

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

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

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

Читайте также:  Почему принтер печатает не ровно текст

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

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

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

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

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

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

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

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

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

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn1. Осуществляя обратную подстановку, далее последовательно находим xn1, xn2, …, x1. Вычисления неизвестных здесь проводятся по формулам

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akk (k – 1) . Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

Рекомендуем к прочтению

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

code

Adblock
detector