Реферат: Численные методы алгебры

Министерство образования и науки РФ

Ульяновский государственный университет

Инженерно-физический факультет высоких технологий

РЕФЕРАТ

Численные методы алгебры

Направление: 21.03.01«Нефтегазовое дело»

Выполнил

студент группы НДМ-В-21/1

С.Н. Ваштахов

Доцент, к.т.н. Е.А. Цынаева

Ульяновск 2021

Содержание

Введение

1. Метод Гаусса

2. Метод простой итерации

3. Метод Зейделя

4. Метод релаксации

5. Метод Ньютона

6. Метод наискорейшего спуска

Введение

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

система линейные алгебраические уравнения гаусс зейдель ньютон

1. Метод Гаусса

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

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

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

Прямой ход состоит из 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-¹⁾ отличен от нуля, вычислим множители k-го шага

q_ik = a_ik^(k-¹⁾ / a_kk^(k-¹⁾ (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⁽ⁿ-¹⁾x_n = b_n⁽ⁿ-¹⁾ .

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

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

x_n = b_n⁽ⁿ-¹⁾ / a_nn⁽ⁿ-¹⁾,

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

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

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

a_ij^(k) = a_ij^(k-¹⁾? q_ika_kj , b_i^(k) = b_i^(k-¹⁾ ? q_ikb_k^(k-¹⁾, 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-м шаге мтода среди элементов a_ij определяют максимальный по модулю элемент a_i1j1. Первое уравнение системы и уравнение с номером i₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_i1 из всех уравнений, кроме первого.

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

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

2. Метод простой итерации

Нелинейные уравнения можно разделить на 2 класса - алгебраические и трансцендентные. Алгебраическими уравнениями называют уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и другие) называются трансцендентными.

Методы решения нелинейных уравнений делятся на две группы:

1. точные методы;

2. итерационные методы.

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

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

Пусть дано уравнение

где:

1. Функция f(x) непрерывна на отрезке [a, b] вместе со своими производными 1-го и 2-го порядка.

2. Значения f(x) на концах отрезка имеют разные знаки (f(a) ? f(b) < 0).

3. Первая и вторая производные f' (x) и f'' (x) сохраняют определенный знак на всем отрезке.

Условия 1) и 2) гарантируют, что на интервале [a, b] находится хотя бы один корень, а из 3) следует, что f(x) на данном интервале монотонна и поэтому корень будет единственным.

Решить уравнение (1) итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.

Всякое значение , обращающее функцию f(x) в нуль, т.е. такое, что: