Метод Гаусса

Date: 2015-10-07; view: 452.

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

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

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

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

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

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

q_i1 = a_i1/a₁₁ (i = 2, 3, …, n),

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q₂₁, q₃₁, …, q_n1. Это позволит обратить в нуль коэффициенты при x₁ во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + … + a_3n⁽¹⁾x_n = b₃⁽¹⁾ ,

. . . . . . . . . . . . . . .

a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + … + a_nn⁽¹⁾x_n = b_n⁽¹⁾ .

в которой a_ij⁽¹⁾ и b_ij⁽¹⁾ вычисляются по формулам

a_ij⁽¹⁾ = a_ij − q_i1a_1j , b_i⁽¹⁾ = b_i − q_i1b₁.

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

q_i2 = a_i2⁽¹⁾ / a₂₂⁽¹⁾ (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q₃₂, q₄₂, …, q_m2. В результате получим систему

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾ = b₂⁽¹⁾ ,

a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

. . . . . . . . . . . . . . . . . . .

a_n3⁽²⁾x₃ + … + a_nn⁽²⁾x_n = b_n⁽²⁾ .

Здесь коэффициенты a_ij⁽²⁾ и b_ij⁽²⁾ вычисляются по формулам

a_ij⁽²⁾ = a_ij⁽¹⁾ – q_i2a_2j⁽¹⁾ , b_i⁽²⁾ = b_i⁽¹⁾ – q_i2b₂⁽¹⁾.

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

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

q_ik = a_ik^(k–1) / a_kk^(k–1) (i = k + 1, …, n)

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

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

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

. . . . . . . . . . . . . . . . . . . .

a_nn^(n–1)x_n = b_n^(n–1) .

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

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение x_n в предпоследнее уравнение, получим x_n–1. Осуществляя обратную подстановку, далее последовательно находимx_n–1, x_n–2, …, x₁. Вычисления неизвестных здесь проводятся по формулам

x_n = b_n^(n–1) / a_nn^(n–1),

x_k = (b_n^(k–1) – a_k,k+1^(k–1)x_k+1 – … – a_kn^(k–1)x_n) / a_kk^(k–1), (k = n – 1, …, 1).

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

1.1.2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

a_ij^(k) = a_ij^(k–1) − q_ika_kj , b_i^(k) = b_i^(k–1) − q_ikb_k^(k–1) , i = k + 1, …, n.

Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей q_ik.

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |q_ik| ≤ 1 для всех k = 1, 2, …, n – 1 иi = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что наk-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk^(k-1). После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления.

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

На 1-м шаге мтода среди элементов a_ij определяют максимальный по модулю элемент a_i1j1. Первое уравнение системы и уравнение с номером i₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_i1 из всех уравнений, кроме первого.

На k-м шаге метода среди коэффициентов a_ij^(k–1) при неизвестных в уравнениях системы с номерами i = k, …, nвыбирают максимальный по модулю коэффициент a_ikjk^(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное x_jk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: x_jn, x_jn–1, …, x_j1.

Метод Крамера состоит в том, что мы последовательно находим главный определитель системы (5.3), т.е. определитель матрицы А

D = det (a_{i j})

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

Формулы Крамера имеют вид:

D × x _i = D _i ( i = ). (5.4)

Из (5.4) следует правило Крамера, которое дает исчерпывающий ответ на вопрос о совместности системы (5.3): если главный определитель системы отличен от нуля, то система имеет единственное решение, определяемое по формулам:

x _i = D _i / D.

Если главный определитель системы D и все вспомогательные определители D _i = 0 (i= ), то система имеет бесчисленное множество решений. Если главный определитель системы D = 0, а хотя бы один вспомогательный определитель отличен от нуля, то система несовместна.

Пример 2.14. Решить методом Крамера систему уравнений:

x₁ + x₂ + x₃ + x₄ = 5,

x₁ + 2x₂ - x₃ + 4x₄ = -2,

2x₁ - 3x₂ - x₃ - 5x₄ = -2,

3x₁ + x₂ +2x₃ + 11 x₄ = 0.

Решение. Главный определитель этой системы

значит, система имеет единственное решение. Вычислим вспомогательные определители D _i ( i = ), получающиеся из определителя D путем замены в нем столбца, состоящего из коэффициентов при x_i, столбцом из свободных членов:

Отсюда x₁ = D ₁/D = 1, x₂ = D ₂/D = 2, x₃ = D ₃/D = 3, x₄ = D ₄/D = -1, решение системы - вектор С=(1, 2, 3, -1)^T.

17. фундаментальная система решений однородной системы линейных уравнений( определения и теорема).

ФУНДАМЕНТАЛЬНАЯ СИСТЕМА РЕШЕНИЙ

линейной однородной системы обыкновенных дифференциальных уравнений - базис векторного пространства действительных (комплексных) решений этой системы. (Система может состоять и из одного уравнения.) Более подробно это определение формулируется следующим образом.
Множество действительных (комплексных) решений {x₁(t),...,x_n(t)}(заданных на нек-ром множестве Е)линейной однородной системы обыкновенных дифференциальных уравнений наз. Ф. с. р. этой системы уравнений (на множестве Е) при выполнении совокупности следующих двух условий: 1) если действительные (комплексные) числа С ₁,..., С _n таковы, что функция C₁x₁(t)+...+C_nx_n(t) тождественно равна нулю на Е, то все числа С ₁,..., С _n равны нулю; 2) для всякого действительного (комплексного) решения х(t)рассматриваемой системы уравнений найдутся действительные (соответственно комплексные) числа С ₁,..., С _n (не зависящие от t)такие, что x(t) = C₁x₁(t)+...+C_nx_n(t) при всех
Если -произвольная невырожденная -матрица, а {x₁(t), ..., х _п(t)}есть Ф. с. р., то также есть Ф. с. р.; всякая Ф. <с. <р. получается таким преобразованием из данной Ф. с. р.
Если система дифференциальных уравнений имеет вид

где (или а (соответственно причем отображение суммируемо на каждом отрезке, содержащемся в - конечный или бесконечный интервал в то векторное пространство решений этой системы изоморфно (соответственно Следовательно, система (1) имеет бесконечно много Ф. с. р., и каждая такая Ф. с. р. состоит из пре шений. Напр., для системы уравнений
произвольная Ф. с. р. имеет вид

где -произвольные линейно независимые векторы-столбцы.
Всякая Ф. с. р. системы (1) имеет вид

где - Коши оператор системы (1), - произвольное фиксированное число из интервала а x₁, . . ., х _п - произвольный фиксированный базис пространства (соответственно
Если система дифференциальных уравнений состоит из одного уравнения

где функции
суммируемы на каждом отрезке, содержащемся в (где - конечный или бесконечный интервал в то векторное пространство решений этого уравнения изоморфно (соответственно Следовательно, уравнение (2) имеет бесконечно много Ф. с. р., и каждая из них состоит из kрешений. Напр., уравнение имеет Ф. с. р. общее действительное решение этого уравнения дается формулой где C₁, С₂ - произвольные действительные постоянные.
Если система дифференциальных уравнений имеет вид

где (или ) и при всяком i = l, ..., k-1 отображение

суммируемо на каждом отрезке, содержащемся в (где -конечный или бесконечный интервал в то пространство решений этой системы уравнений изоморфно (соответственно Ф. с. р. системы (3) существуют, и каждая из них состоит из knрешений.
Для линейных однородных систем дифференциальных уравнений, не разрешенных относительно старших производных, даже если коэффициенты системы постоянные, число решений, входящих в Ф. с. р. (т. е. размерность векторного пространства решений), вычисляется иногда не столь просто, как в вышеприведенных случаях. (В [1], з 11 рассмотрено такое вычисление для линейных систем дифференциальных уравнений с постоянными коэффициентами, не разрешенных относительно старших производных.)

18. векторы на плоскости и в пространстве.

Вектор – это направленный отрезок прямой.

То есть, в качестве вектора мы принимаем отрезок на плоскости или в пространстве, считая одну из его граничных точек началом, другую – концом.

Для обозначения векторов будем использовать строчные латинские буквы со стрелочкой над ними, например . Если заданы граничные точки начала и конца отрезка, к примеру А и В, то вектор будем обозначать как .

Определение.

Нулевой вектор – это любая точка плоскости или пространства.

Будем считать, что нулевому вектору можно придать любое направление на плоскости и в пространстве.

Определение.

Длина вектора - это неотрицательное число, равное длине отрезка АВ.

Длину вектора будем обозначать как .

Так как обозначение длины вектора в точности совпадает со знаком модуля, то можно услышать, что длину вектора называют модулем вектора. Все же рекомендуем использовать термин "длина вектора". Длина нулевого вектора равна нулю.

Определение.

Два вектора называют коллинеарными, если они лежат либо на одной прямой, либо на параллельных прямых.

Определение.

Два вектора называют неколлинеарными, если они не лежат на одной прямой или параллельных прямых.

Нулевой вектор коллинеарен любому другому вектору.

Определение.

Два коллинеарных вектора и называют сонаправленными, если их направления совпадают и обозначают .

Определение.

Два коллинеарных вектора и называют противоположно направленными, если их направления противоположны и обозначают ).

Будем считать, что нулевой вектор сонаправлен с любым другим вектором.

Определение.

Два вектора называются равными, если они сонаправленные и их длины равны.

Определение.

Два вектора называются противоположными, если они противоположно направлены и их длины равны.

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

Пусть и два произвольных вектора на плоскости или в пространстве. Отложим от некоторой точки O плоскости или пространства векторы и . Лучи OA и OBобразуют угол .

Определение.

Угол называется углом между векторами и .

Угол между сонаправленными векторами равен нулю градусам (или нулю радиан), а угол между противоположно направленными векторами равен 180 градусам (или радиан).

Определение.

Два вектора называются перпендикулярными, если угол между ними равен 90градусам (или радиан).