Точные и приближенные методы решения систем линейных алгебраических уравнений (3 видео)

Точные и приближенные методы решения систем линейных уравнений

Дата добавления: 2015-06-12 ; просмотров: 5321 ; Нарушение авторских прав

Самое простое уравнение — это линейное уравнение с одной переменной х вида:

Обобщением таких уравнений является линейное уравнение с несколькими переменными х₁, х₂, . х_n вида:

Многие задачи сводятся к решению конечного множества уравнений вида (2), то есть системы линейных уравнений. В общем виде система n линейных уравнений с n переменными x₁, x₂. x_n записывается как совокупность числовых равенств:

(3)

Коэффициенты a_ij системы для их упорядочения снабжаются двумя индексами, причем индекс i соответствует номеру строки, а j —номеру столбца (i = 1, 2. n; j = 1, 2. n). Тогда свободный член запишется в виде b_i(i = 1, 2. n), а переменная— х_j (j = 1, 2. n). Будем далее считать, что упорядоченные наборы чисел a_ij, x_j и b_i берутся из множества действительных чисел R. Решением системы (3) n уравнений с n переменными называют упорядоченную совокупность n чисел c₁, c₂, . c_n. являющуюся решением каждого из уравнений, входящих в систему. Ясно, что эта совокупность чисел при подстановке ее в систему (3) вместо х₁, х₂, . х_n обращает каждое уравнение системы в истинное числовое равенство. Таким образом, множество решений системы является пересечением множеств решений, входящих в систему уравнений.

В частном случае, при n = 2 и n = 3 получаем хорошо знакомые системы двух линейных уравнений с двумя переменными:

(4)

и трех линейных уравнений с тремя переменными:

(5)

Решением системы (4) является упорядоченная пара чисел (c₁, c₂), а решением системы (5) — упорядоченная тройка чисел (с₁, c₂, c₃).

Известно, что исследование и нахождение решения для систем (4) и (5) не представляют особых трудностей. Но задачи практического содержания сводятся к исследованию и решению систем линейных уравнений, содержащих десятки, сотни и даже тысячи переменных. Число элементарных операций при решении линейных систем с n переменными пропорционально примерно n 3 , поэтому решение таких задач стало возможным только с появлением быстродействующих ЭВМ.

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

Методы решения систем линейных уравнений можно разделить на две группы: точные и итерационные (приближенные) методы.

Точными являются такие методы, которые позволяют получить решение системы после выполнения конечного числа арифметических операций над коэффициентами системы и их свободными членами. Причем решение получится точным только тогда, когда коэффициенты и правые части системы (3) известны точно и все арифметические действия над ними выполняются без округлений. Из точных методов рассмотрим метод Гаусса и правило Крамера. Однако на практике даже этими методами не всегда удается получить точное решение, ибо в ЭВМ точные коэффициенты представляются приближенно с некоторой погрешностью, а в процессе вычислений необходимо проводить округление чисел.

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

4.1 Алгоритм метода Гаусса

Пусть дана система n линейных уравнений с n переменными:

Коэффициенты а_ij при переменных будем рассматривать как элементы двумерного массива A (N, N), а свободные члены b_i— как элементы одномерного массива В (N). Решение x_i(i = ) разместим в одномерном массиве В (N). Коэффициенты а_ij и свободные члены b_i будем рассматривать как элементы расширенной матрицы

Предписываемые методом Гаусса преобразования будем выполнять над элементами расширенной матрицы. Опишем формально алгоритм решения линейной системы методом Гаусса без выбора главного элемента.

1. Элементы первой строки расширенной матрицы (А | В)делим на а₁₁. Полученную после такого деления первую строку умножаем последовательно на a_k1(k = ) и вычитаем ее затем из k-ой строки (k = ). После этого преобразования в первом столбце массива A (кроме ) все элементы будут равны нулю, то есть получим матрицу:

2. Элементы второй строки расширенной матрицы делим на , затем умножаем ее последовательно на и вычитаем из оставшихся строк при

3. Продолжаем этот процесс исключения переменных (получения нулей) до тех пор, пока подобная процедура не будет проделана с (n — 1)-й строкой матрицы. После этого получим матрицу:

4. Элементы n-й строки делим на и в результате получаем:

На этом закончился прямой ход метода Гаусса.

5. Выполняем обратный ход метода Гаусса: в (п—1)-ю строку последней матрицы подставляем значение х_n и находим значение x_n-1, затем последовательно находим x_n-2, x_n-3, . , x₂, x₁ по формулам:

Этот алгоритм является экономичным в смысле использования памяти, так как все промежуточные и окончательные значения элементов в процессе преобразования матриц последовательно хранятся в тех же ячейках памяти, что и массивы А и В. Очередные значения диагональных элементов перед началом преобразования строк будем присваивать простой переменной D, что позволит хранить их до окончания преобразования очередной строки матрицы.

Значения переменных x_n, x_n-1, . x₁ присваиваются элементам массива свободных членов В.

Метод Гаусса с выбором главного элементазаключается в том,что при прямом ходе производится выбор наибольшего по модулю (главного) элемента и перестановка строк или столбцов. Последнее исключает деление на 0, если матрица коэффициентов содержит нулевые элементы, и повышает точность вычислений при наличии ошибок округления. Обычно для программ, ведущих вычисления с числами с плавающей точкой, достаточен выбор A_ii ¹ 0.

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

4.2 Правило Крамера

Правило Крамера рассмотрим на примере двух линейных уравнений с двумя переменными:

(17)

хотя оно применимо и для решения системы n линейных уравнений с n переменными, но с увеличением n требует большого объема вычислительной работы.

Умножим первое уравнение системы (17) на коэффициент а₂₂, а второе — на — a₁₂ и полученные уравнения сложим. Тогда имеем:

Если a₁₁a₂₂ — a₂₁a₁₂ 0, то получаем значение переменной

Аналогично, умножая первое уравнение системы (17) на —a₂₁, второе — на а₁₁ и складывая их, получаем:

Введем обозначения: a₁₁a₂₂ — a₂₁a₁₂ = = ;

b₁a₂₂ — b₂a₁₂ =

a₁₁b₂ — a₂₁b₁ =

Следовательно, — определитель матрицы коэффициентов системы (17). Определитель получается из определителя , если коэффициенты системы (17) при x₁ (первый столбец матрицы А) заменить свободными членами

B = ;

Определитель — если заменить коэффициенты системы (17) при x₂ (второй столбец матрицы А) свободными членами.

Определитель называется главным определителем системы (17), а определители ₁ и ₂ — вспомогательными.

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

Таким образом, если главный определитель системы уравнений (17) , то система имеет единственное решение, определяемое формулами

(18)

Формулы (18) называются формулами Крамера.

Нахождение решения линейной системы (17) по формулам (18) называется правилом Крамера, который одним из первых пришел к понятию определителя и доказал сформулированное выше предложение.

Справедливы также следующие два предложения:

1. Если главный определитель системы (17) = 0, но хотя бы один из вспомогательных определителей ₁ или ₂ отличен от нуля, то система (17) не имеет решений (система несовместна).

2. Если все три определителя , ₁ и ₂ системы (17) равны нулю, но среди коэффициентов а_ij(i, j = 1,2) есть хотя бы один, отличный от нуля, то система (17) имеет бесконечное множество решений.

Легко дать геометрическое истолкование этим предложениям. Поскольку каждому уравнению системы (17) в плоскости соответствует некоторая прямая, то система (17) имеет единственное решение, если прямые имеют одну общую точку; не имеет решений, если прямые параллельны; и имеет бесконечное множество решений, если прямые сливаются.

Правило Крамера решения системы n линейных уравнений с n переменными имеет определенное теоретическое значение; практически им уже при n = 4 не пользуются. Установлено, что число операций умножения и деления, которые необходимо выполнить при решении линейной системы алгебраических уравнений порядка n по формулам Крамера, равно:

N(n)= (n 2 — 1)n! + n,

а по схеме единственного деления метода Гаусса:

N(n) = (n 2 + 3n — 1).

Для сравнения объема вычислительной работы по этим двум алгоритмам подсчитаем количество операций:

по Крамеру по Гауссу

при n = 5 2885 65

при n =10 360*10 6 430

Поэтому все современные ЭВМ имеют стандартные подпрограммы, реализующие различные модификации метода Гаусса.

4.3 Метод итераций и метод Зейделя

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

. (19)

Предположим, что определитель системы отличен от нуля и что диагональные коэффициенты

Выразим из первого уравнения x₁, из второго x₂, и т. д. Тогда получим эквивалентную систему:

где

Полученную систему запишем так:

(20)

и назовем ее системой нормального вида.

Будем решать ее методом последовательных приближений. За нулевое приближение возьмем, например, столбец свободных членов

Подставив в правую часть системы (20) значения (i = ), получим первое приближение: .

Затем аналогично второе: и т. д.

Таким образом, зная k-e приближение, (k + 1)-е приближение вычисляют по формуле (21)

Если последовательность приближений ( ) (j = ) имеет предел

то является точным решением системы нормального вида, а значит, и исходной системы. В самом деле, переходя к пределу при в (21), имеем:

Описанный метод последовательных приближений называется методом итераций. Рабочие формулы метода итераций имеют вид:

(22)

гарантирует теорема о достаточном признаке сходимости процесса итераций.

Достаточным условием сходимости итерационных методов является условие

При методе Зейделя итерационный процесс подобен описанному для метода простых итераций, однако уточненные значения Х_i j+1 сразу подставляются в последующие уравнения. Формула итерационного процесса имеет вид:

Содержание

Точные и приближенные методы решения систем линейных уравнений. Метод итераций
Методы решения систем линейных алгебраических уравнений (СЛАУ) с примерами
Методы решения систем линейных алгебраических уравнений (СЛАУ)
Метод Крамера
Матричный способ решения СЛАУ
Метод Гаусса
Ранг матрицы. Теорема Кронекера-Капелли
Следствия из теоремы Кронекера — Капелли
📹 Видео

Видео:Решение системы уравнений методом ГауссаСкачать

Точные и приближенные методы решения систем линейных уравнений. Метод итераций

Численный метод решения задачи называется точным, если при точном выполнении всех требуемых действий мы получаем точное решение системы. При этом имеется в виду, что все коэффициенты, данные и параметры задачи представляют собой точные значения. Заметим, что методы Гаусса и Жордана — Гаусса, основанные на процессе исключения неизвестных, являются точными.

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

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

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

Далее кратко рассмотрим метод итераций (к слову, он гораздо проще реализуется в среде Microsoft Excel, чем метод Жордана — Гаусса). Сущность метода изложим на примере системы трех линейных уравнений с тремя неизвестными.

Пусть дана система трех линейных уравнений с тремя неизвестными. Для применения метода итераций приведем систему к виду

Систему вида (3.14) будем называть системой нормального вида. Пусть (х₀; j₀; z₀) есть некоторое грубо приближенное решение системы. Назовем эту совокупность чисел начальным приближением. Если какое-либо грубое приближение неизвестно, то за него можно взять вообще произвольную совокупность значений неизвестных и принять его за начальное приближение. Часто за начальное приближение берут совокупность свободных членов: (Dp, Dp, D₃). Подставим числа х₀, у₀, 2 о в правые части системы (3.14). В левых частях системы (3.14) получаем некоторые значения переменных х, у, z. Обозначим ихх_ьу_ь z_x и назовем первым приближением. Подставив числа х_1; у_г, z_x в правые части системы (3.14), получим второе приближение: х₂, y₂, z₂. Этот процесс можно осуществлять неограниченно. При некоторых условиях, налагаемых на коэффициенты А_ь В _ь Ci,A₂,. С₃, к-е приближение х_к, у_к, z_k при возрастании к будет становиться сколь угодно близким к истинному решению системы (х; у*; z»).

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

Заметим, что систему (3.14) и аналогичные системы п линейных уравнений с п неизвестными можно записать в матричном виде. Обозначим

Тогда систему (3.14) и аналогичные ей системы п линейных уравнений с п неизвестными можно записать так:

Сформулируем теперь достаточные условия сходимости итерационного процесса.

Достаточные условия сходимости итерационного процесса:

1. Сумма модулей элементов каждой строки матрицы А (сумма модулей коэффициентов каждого уравнения системы (3.14)) меньше единицы.
2. Сумма квадратов всех элементов каждой строки матрицы А (сумма квадратов коэффициентов каждого уравнения системы (3.14)) меньше единицы.

Найдите решение системы линейных алгебраических уравнений

методом итераций с точностью до 10 -7 .

Найдем сумму модулей коэффициентов при неизвестных в каждом уравнении.

В первом уравнении: 0,12 + 0,18 + 0,08 = 0,38.

Во втором уравнении: 0,15 + 0,06 + 0,11 = 0,32.

В третьем уравнении: 0,04 + 0,10 + 0,09 = 0,23.

Для каждого из уравнений эта сумма меньше единицы, значит, итерационный процесс сходится, и мы можем получить приближенное решение системы методом итераций. Откроем файл «Численные методы линейной алгебры» (Microsoft Excel). Переименуем лист 3 в лист «Метод итераций». Объединим ячейки А1—F1 и поместим туда надпись Начальное приближение. Объединим ячейки Gl—II и поместим туда надпись Матрица системы. В ячейку Л поместим надпись Свободные члены. В ячейки диапазона G2—14 поместим матрицу Л системы, а в ячейки диапазона J2—J4 — свободные члены системы. В ячейку А2 поместим х0=, в ячейку С2 поместим у0=, в ячейку F2 поместим z0=. В ячейки В2, D2 и F2 поместим начальные приближения решения, равные свободным членам системы: -0,64; 0,26; 1,34 соответственно.

Теперь в ячейку АЗ поместим х1=, в ячейку СЗ поместим у1=, в ячейку F3 поместим zl=. В ячейку ВЗ поместим формулу =$G$2*B2+$H$2*D2+$I$2*F2+$J$2 , в ячейку D3 поместим формулу

=$G$3*B2+$H$3*D2+$I$3*F2+$J$31, а в ячейку F3 — формулу

Рис. ЗА. Решение систем линейных уравнений методом итераций

| =$G$4*B2+$H$4*D2+$I$4*F2+$J$4 1. Скопируем ячейки диапазона A3—F3 и последовательно вставляем их вниз до тех пор, пока два соседних значения в каждом из столбцов не станут равными. Эти значения и будут нужными приближениями. Исправляем нумерацию индексов в нужных ячейках столбцов А, С и Е и получаем значения (рис. 3.4):

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

Видео:Базисные решения систем линейных уравнений (03)Скачать

Методы решения систем линейных алгебраических уравнений (СЛАУ) с примерами

Содержание:

Видео:Метод Крамера за 3 минуты. Решение системы линейных уравнений - bezbotvyСкачать

Методы решения систем линейных алгебраических уравнений (СЛАУ)

Метод Крамера

Определение: Системой линейных алгебраических уравнений (СЛАУ) называется выражение

Определение: Определитель, составленный из коэффициентов при неизвестных, называется главным определителем системы

Крамер предложил следующий метод решения СЛАУ: умножим главный определитель на для этого умножим все элементы первого столбца на эту неизвестную:

Второй столбец умножим на третий столбец — на -ый столбец — на и все эти произведения прибавим к первому столбцу, при этом произведение не изменится:

Согласно записи СЛАУ первый столбец получившегося определителя представляет собой столбец свободных коэффициентов, т.е.

Определение: Определитель называется первым вспомогательным определителем СЛАУ.

Поступая аналогично тому, как описано выше, найдем все вспомогательные определители СЛАУ:

31. Для того чтобы найти вспомогательный определитель i, надо в главном определителе СЛАУ заменить столбец i на столбец свободных коэффициентов.

Определение: Полученные выше соотношения называются формулами Крамера. Используя формулы Крамера, находят неизвестные величины Проанализируем полученные формулы:

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

Пример:

Решить СЛАУ методом Крамера

Решение:

Прежде всего, обращаем внимание на то, что в последнем уравнении переменные записаны в неправильном порядке, в этом случае говорят, что СЛАУ записана в ненормализованном виде. Нормализуем СЛАУ, для чего запишем неизвестные в последнем уравнении системы в правильном порядке, чтобы одноименные неизвестные были записаны друг под другом

Найдем главный определитель СЛАУ (раскрываем по первой строке)

Так как главный определитель системы отличен от нуля, то СЛАУ имеет единственное решение. Найдем три вспомогательных определителя

Воспользуемся формулами Крамера

Замечание: После нахождения решения СЛАУ надо обязательно провести проверку, для чего найденные числовые значения неизвестных подставляется в нормализованную систему линейных алгебраических уравнений.

Выполним проверку Отсюда видно, что СЛАУ решена верно.

Матричный способ решения СЛАУ

Для решения СЛАУ матричным способом введем в рассмотрение матрицу, составленную из коэффициентов при неизвестных матpицы-столбцы неизвестных и свободных коэффициентов

Тогда СЛАУ можно записать в матричном виде Матричный способ решения СЛАУ состоит в следующем: умножим слева матричное уравнение на обратную матрицу к матрице А, получим в силу того, что произведение найдем Таким образом, для нахождения неизвестных матричным способом, надо найти обратную к А матрицу после чего надо умножить эту матрицу на матрицу-столбец свободных коэффициентов.

Пример:

Решить СЛАУ матричным способом

Решение:

Введем в рассмотрение следующие матрицы

Найдем матрицу (см. Лекцию № 2): найдем детерминант матрицы А.

Пример:

Решение:

Найдем алгебраические дополнения всех элементов Запишем обратную матрицу (в правильности нахождения обратной матрицы убедиться самостоятельно). Подействуем пай денной матрицей на матрицу-столбец свободных коэффициентов В:

Отсюда находим, что х = 1; y = l; z = l.

Метод Гаусса

Метод Гаусса или метод исключения неизвестных состоит в том, чтобы за счет элементарных преобразований привести СЛАУ к треугольному виду. Покажем использование расширенной матрицы, составленной из коэффициентов при неизвестных и расширенной за счет столбца свободных коэффициентов, для приведения СЛАУ к треугольному виду на примере системы, рассматриваемой в этой лекции. Расширенная матрица для СЛАУ имеет вид:

Замечание: В методе Гаусса желательно, чтобы первая строка расширенной матрицы начиналась с единицы.

Обменяем в расширенной матрице первую и вторую строки местами, получим Приведем матрицу к треугольному виду, выполнив следующие преобразования: умножим элементы первой строки на (-2) и прибавим к соответствующим элементам второй строки Разделим все элементы второй строки на (-5), получим эквивалентную матрицу

Умножим элементы первой строки на (—1) и прибавим к соответствующим элементам третьей строки Разделим все элементы третьей строки на (-3), получим Таким образом, эквивалентная СЛАУ имеет вид (напомним, что первый столбец это коэффициенты при неизвестной х, второй — при неизвестной у, третий — при неизвестной z, а за вертикальной чертой находится столбец свободных коэффициентов):

Из первого уравнения находим, что х = 1.

Вывод: Из вышеизложенного материала следует, что вне зависимости от

способа решения СЛАУ всегда должен получаться один и тот же ответ.

Замечание: После нахождения решения СЛАУ надо обязательно выполнить проверку, то есть подставить полученные значения неизвестных в заданную СЛАУ и убедиться в тождественности левой части всех равенств системы соответствующим правым частям. Отметим, что задание СЛАУ всегда верно, то есть, если проверка показывает нарушение оговоренной тождественности, то надо искать ошибку в проведенных вычислениях.

Ранг матрицы. Теорема Кронекера-Капелли

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

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

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

Пример:

Найти ранг матрицы

Решение:

Очевидно, что среди миноров второго порядка есть миноры отличные от нуля, например, среди миноров третьего порядка также есть миноры, которые не равны нулю, например, Очевидно, что определитель четвертого порядка равен нулю, так как он будет содержать строку, состоящую из одних нулей (см. свойство для определителей). Следовательно, ранг матрицы А равен 3.

Теорема Кронекера-Капелли (критерий совместности СЛАУ). Для совместности системы линейных алгебраических уравнений (СЛАУ) необходимо и достаточно, чтобы ранг расширенной матрицы совпадал с рангом основной матрицы, составленной из коэффициентов при неизвестных величинах.

Видео:2.2 Итерационные методы решения СЛАУ (Якоби, Зейделя, релаксации)Скачать

Следствия из теоремы Кронекера — Капелли

Следствие: Если ранг матрицы совместной системы равен числу неизвестных, то система имеет единственное решение (то есть она определенная).

Следствие: Если ранг матрицы совместной системы меньше числа неизвестных, то система имеет бесчисленное множество решений (т.е. она неопределенная).

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

Рекомендую подробно изучить предметы:

Математика
Алгебра
Линейная алгебра
Векторная алгебра
Высшая математика
Дискретная математика
Математический анализ
Математическая логика

Ещё лекции с примерами решения и объяснением:

Скалярное произведение и его свойства
Векторное и смешанное произведения векторов
Преобразования декартовой системы координат
Бесконечно малые и бесконечно большие функции
Критерий совместности Кронекера-Капелли
Формулы Крамера
Матричный метод
Экстремум функции

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Telegram и логотип telegram являются товарными знаками корпорации Telegram FZ-LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.