ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.12.2023
Просмотров: 67
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
x2
x*
A1
A2
x
y
Напишем общее уравнение прямой, проходящей через две точки М1(x1, y1) и М2(x2, y2):
(М1М2):
Используя это уравнение, проведем хорду через точки А(а, f(а)) и B(b, f(b)):
возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x1.
, отсюда
, или
Проведем хорду через точки А(х1, f(х1)) и B(b, f(b)):
возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x2.
отсюда
или
Полученная таким образом последовательность x0, x1, x2, … имеет своим пределом искомый корень.
Вывод:
II случай:
f (x) и f (x) имеют разные знаки.
a
b
x*
x2
x1
x
y
B2
B1
B
f (x) < 0
f (x) 0
A
, у = 0, x = x1
, отсюда
, или
Проведем хорду через точки А(a, f(a)) и B(x1, f(x1)):
, возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x2.
, отсюда
, или
Полученная таким образом последовательность x0, x1, x2, … имеет своим пределом искомый корень.
Вывод:
В качестве начального приближения x0 надо взять тот конец [a, b], в котором знак f(x) и знак f (x) противоположны.
Оценка погрешности и условие окончания вычислений такие же, что и в методе касательных.
г) комбинированное применение методов хорд и касательных
Необходимо найти действительный корень уравнения f(x) = 0, изолированный на отрезке [a, b].
Предполагается, что f(а) и f(b) имеют разные знаки, а каждая из производных сохраняет определенный знак на отрезке изоляции.
Возьмем на отрезке [a, b] такую точку x0, что f(x0) и f (x0) имеют одинаковые знаки.
Воспользуемся формулами методов хорд и касательных:
Величины x11 и x12 принадлежат промежутку изоляции, причем f(x11) и f(x12) имеют разные знаки.
Построим новую пару приближений к корню:
Точки x21 и x22 на числовой оси расположены между точками x11 и x12, причем f(x21) и f(x22) имеют разные знаки.
Вычислим теперь значения:
и т.д.
Каждая из последовательностей
x11, x21, x31, …, xn1, … и x12, x22, x32, …, xn2, …
стремится к искомому корню, причем одна из последовательностей монотонно возрастает, а другая монотонно убывает.
Пусть – приближенное значение корня, полученное на n-ом шаге методом касательных, а – приближенное значение корня, полученное на n-м шаге методом хорд.
Тогда условием окончания вычисления будет:
а
§1. Постановка задачи
Рассмотрим систему из n линейных уравнений с n неизвестными
(1)
Предположим, что система имеет единственное решение.
Найти решение системы А, т.е. с заданной точностью.
I. Точные (Прямые) методы
Точные (Прямые) методы – это методы, которые приводят к решению за конечное число арифметических операций.
а) Формулы Крамера:
Запишем систему (1) в матричном виде: АX = В, где
– матрица системы;
– вектор (столбец) неизвестных;
– вектор (столбец) свободных членов.
Потребуем от системы выполнение определенных условий:
1. Матрица А должна быть размерностью nn;
2. det A 0.
Тогда при небольших n можем использовать формулы Крамера:
, (i = 1, 2, 3, … , n) (2)
где Ai – матрица nn, получена из матрицы системы А заменой i-го столбца столбцом свободных членов.
При использовании формулы Крамера необходимо вычислить (n + 1) определителей.
Если определители вычислять разложением по строке (столбцу), то на вычисление определителя n-го порядка будет затрачиваться n! операций умножения.
Факториальный рост числа операций с увеличением размерности n называется проклятием размерности (100! 10158), а размерность n = 100 для современных задач не велика.
б) Метод Гаусса.
Последовательное исключение неизвестных.
Выпишем расширенную матрицу.
(3)
Предположим, что коэффициент a11, называемый ведущим элементом первой строки, не равен нулю. Разделив первую сроку на a11, получим
где
С помощью первой строки получаем в первом столбце, начиная со второй строки, нули. Для этого, сложим первую строку со следующими строками. Умножив ее на элементы аi1 (i
= 2, 3, …, n) с противоположным знаком.
где
Допустим, что ведущий элемент второй строки, т.е. коэффициент a22(1), тоже отличен от нуля. Тогда, разделив на него вторую сроку, получим
С помощью второй строки получаем во втором столбце ниже единицы все нули. Получаем
и т.д.
В результате получим
(4)
Переход от расширенной матрицы к матрице (4) называется прямой ход метода Гаусса (получение треугольной матрицы).
С помощью последней строки, получаем в последнем столбце все нули выше единицы.
Затем с помощью предпоследней строки в предпоследнем столбце получаем нули выше единицы и т.д.
Получим
Это преобразование называется – обратный ход метода Гаусса (переход от треугольной матрицы к единичной).
(5)
– решение системы (1).
в) Метод Гаусса с выбором главного элемента
Рассмотренный выше простейший вариант метода Гаусса, называемый схемой единственного деления, обладает следующими недостатками.
Если делить на число, близкое к нулю, то получится большая ошибка округления, поэтому если на диагонали матрицы стоят числа близкие к нулю, то приблизительное решение системы получаются с большой погрешностью.
Чтобы уменьшить ошибки округления, используют метод Гаусса с выбором главного элемента.
Пусть дана система (1).
Выпишем расширенную матрицу.
В первом столбце среди всех элементов выбираем наибольший по модулю элемент и ту строку, в которой он находится, меняем местами с первой строкой.
Затем во втором столбце среди элементов, начиная со второго, выбираем наибольший по модулю элемент и строку, в которой он находится, меняем со второй строкой и т.д.
Затем как в методе Гаусса получаем в первом столбце первой строки единицу, а ниже ее нули.
Обратный ход тот же, что и в методе Гаусса.
Прямые методы приводят к точным решениям, если все вычисления производились без округлений.
Невязкой решения называется вектор
который равен |AX 0 – B|.
,
1 = |a11 x10 + a12 x20 + … + a1n xn0 – b1|
По малости невязки решения можно с осторожностью судить о близости найденного приближенного решения x0 и точного решения x*.
Замечание. Правило Крамера в ЭВМ не применяется, т.к. оно требует значительно большего числа арифметических действий, чем метод Гаусса. Метод Гаусса используется в ЭВМ при решении систем до порядка 103, а итерационные методы – до порядка 106.
n = | an1 x10 + an2 x20 + … + ann xn0 – bn|
2 = |a21 x10 + a22 x20 + … + a2n xn0 – b2|
……………………………………….
Итерационные методы – это методы, в которых точное решение может быть получено лишь в результате бесконечного повторения единообразных, как правило, простых действий.
а) метод простых итераций.
Предположим, что диагональные элементы системы (1) не равны 0 (аij 0). Из первого уравнения выражаем х1, из второго – х2 и т.д. Из n-ого – хn.
Обозначим
,
(6)
Система (6) приведена к нормальному виду. Запишем ее в матричном виде: X = + x, где
,
,
х0 = – нулевое приближение. Общая формула имеет вид:
Будем решать систему (6) методом последовательных приближений.
хk+1 = хk +
т.е. х0 = ; х(1) = х(0) + ; х(2) = х(1) + …
Теорема 1. Если максимальная сумма модулей коэффициентов при неизвестных в правой части каждого уравнения системы (6) меньше единицы, то последовательность приближений имеет предел.
Если последовательность приближений имеет предел, то
– точное решение системы (6) следовательно, системы (1).
Теорема 2. Необходимым и достаточным условием сходимости метода простых итераций при любом начальном векторе x0 к решению x* системы (6) является требование, чтобы все собственные числа матрицы были по модулю меньше 1.
Условие окончания вычисления.
Пусть
– точное решение системы.
– k-ое приближенное значение неизвестных, вычисленных по методу итераций.
Тогда | xi(k+1) – xi(k) | < для любого i = 1, 2, … , n.
Оценка погрешности:
Определим:
(Норма)
|| || = max {|1|, |2|, …, |n|}
Тогда
max {| x1 – x1(k) |, | x2 – x2(k) |, …, | xn – xn(k) |}
Пример. Показать, что для данной системы итерационный процесс сходится и определить, сколько итераций следует выполнить, чтобы найти неизвестные с точностью = 10–4.
|||| = max {0,42; 0,55; 0,4} 1
|||| = 0,55 – итерационный процесс сходится.
x*
A1
A2
x
y
Напишем общее уравнение прямой, проходящей через две точки М1(x1, y1) и М2(x2, y2):
(М1М2):
Используя это уравнение, проведем хорду через точки А(а, f(а)) и B(b, f(b)):
возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x1.
, отсюда
, или
Проведем хорду через точки А(х1, f(х1)) и B(b, f(b)):
возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x2.
отсюда
или
Полученная таким образом последовательность x0, x1, x2, … имеет своим пределом искомый корень.
Вывод:
II случай:
f (x) и f (x) имеют разные знаки.
a
b
x*
x2
x1
x
y
B2
B1
B
f (x) < 0
f (x) 0
A
, у = 0, x = x1
, отсюда
, или
Проведем хорду через точки А(a, f(a)) и B(x1, f(x1)):
, возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x2.
, отсюда
, или
Полученная таким образом последовательность x0, x1, x2, … имеет своим пределом искомый корень.
Вывод:
В качестве начального приближения x0 надо взять тот конец [a, b], в котором знак f(x) и знак f (x) противоположны.
Оценка погрешности и условие окончания вычислений такие же, что и в методе касательных.
г) комбинированное применение методов хорд и касательных
Необходимо найти действительный корень уравнения f(x) = 0, изолированный на отрезке [a, b].
Предполагается, что f(а) и f(b) имеют разные знаки, а каждая из производных сохраняет определенный знак на отрезке изоляции.
Возьмем на отрезке [a, b] такую точку x0, что f(x0) и f (x0) имеют одинаковые знаки.
Воспользуемся формулами методов хорд и касательных:
Величины x11 и x12 принадлежат промежутку изоляции, причем f(x11) и f(x12) имеют разные знаки.
Построим новую пару приближений к корню:
Точки x21 и x22 на числовой оси расположены между точками x11 и x12, причем f(x21) и f(x22) имеют разные знаки.
Вычислим теперь значения:
и т.д.
Каждая из последовательностей
x11, x21, x31, …, xn1, … и x12, x22, x32, …, xn2, …
стремится к искомому корню, причем одна из последовательностей монотонно возрастает, а другая монотонно убывает.
Пусть – приближенное значение корня, полученное на n-ом шаге методом касательных, а – приближенное значение корня, полученное на n-м шаге методом хорд.
Тогда условием окончания вычисления будет:
а
§1. Постановка задачи
Рассмотрим систему из n линейных уравнений с n неизвестными
(1)
Предположим, что система имеет единственное решение.
Найти решение системы А, т.е. с заданной точностью.
I. Точные (Прямые) методы
Точные (Прямые) методы – это методы, которые приводят к решению за конечное число арифметических операций.
а) Формулы Крамера:
Запишем систему (1) в матричном виде: АX = В, где
– матрица системы;
– вектор (столбец) неизвестных;
– вектор (столбец) свободных членов.
Потребуем от системы выполнение определенных условий:
1. Матрица А должна быть размерностью nn;
2. det A 0.
Тогда при небольших n можем использовать формулы Крамера:
, (i = 1, 2, 3, … , n) (2)
где Ai – матрица nn, получена из матрицы системы А заменой i-го столбца столбцом свободных членов.
При использовании формулы Крамера необходимо вычислить (n + 1) определителей.
Если определители вычислять разложением по строке (столбцу), то на вычисление определителя n-го порядка будет затрачиваться n! операций умножения.
Факториальный рост числа операций с увеличением размерности n называется проклятием размерности (100! 10158), а размерность n = 100 для современных задач не велика.
б) Метод Гаусса.
Последовательное исключение неизвестных.
Выпишем расширенную матрицу.
(3)
Предположим, что коэффициент a11, называемый ведущим элементом первой строки, не равен нулю. Разделив первую сроку на a11, получим
где
С помощью первой строки получаем в первом столбце, начиная со второй строки, нули. Для этого, сложим первую строку со следующими строками. Умножив ее на элементы аi1 (i
= 2, 3, …, n) с противоположным знаком.
где
Допустим, что ведущий элемент второй строки, т.е. коэффициент a22(1), тоже отличен от нуля. Тогда, разделив на него вторую сроку, получим
С помощью второй строки получаем во втором столбце ниже единицы все нули. Получаем
и т.д.
В результате получим
(4)
Переход от расширенной матрицы к матрице (4) называется прямой ход метода Гаусса (получение треугольной матрицы).
С помощью последней строки, получаем в последнем столбце все нули выше единицы.
Затем с помощью предпоследней строки в предпоследнем столбце получаем нули выше единицы и т.д.
Получим
Это преобразование называется – обратный ход метода Гаусса (переход от треугольной матрицы к единичной).
(5)
– решение системы (1).
в) Метод Гаусса с выбором главного элемента
Рассмотренный выше простейший вариант метода Гаусса, называемый схемой единственного деления, обладает следующими недостатками.
Если делить на число, близкое к нулю, то получится большая ошибка округления, поэтому если на диагонали матрицы стоят числа близкие к нулю, то приблизительное решение системы получаются с большой погрешностью.
Чтобы уменьшить ошибки округления, используют метод Гаусса с выбором главного элемента.
Пусть дана система (1).
Выпишем расширенную матрицу.
В первом столбце среди всех элементов выбираем наибольший по модулю элемент и ту строку, в которой он находится, меняем местами с первой строкой.
Затем во втором столбце среди элементов, начиная со второго, выбираем наибольший по модулю элемент и строку, в которой он находится, меняем со второй строкой и т.д.
Затем как в методе Гаусса получаем в первом столбце первой строки единицу, а ниже ее нули.
Обратный ход тот же, что и в методе Гаусса.
Прямые методы приводят к точным решениям, если все вычисления производились без округлений.
Невязкой решения называется вектор
который равен |AX 0 – B|.
,
1 = |a11 x10 + a12 x20 + … + a1n xn0 – b1|
По малости невязки решения можно с осторожностью судить о близости найденного приближенного решения x0 и точного решения x*.
Замечание. Правило Крамера в ЭВМ не применяется, т.к. оно требует значительно большего числа арифметических действий, чем метод Гаусса. Метод Гаусса используется в ЭВМ при решении систем до порядка 103, а итерационные методы – до порядка 106.
n = | an1 x10 + an2 x20 + … + ann xn0 – bn|
2 = |a21 x10 + a22 x20 + … + a2n xn0 – b2|
……………………………………….
II. Итерационные методы
Итерационные методы – это методы, в которых точное решение может быть получено лишь в результате бесконечного повторения единообразных, как правило, простых действий.
а) метод простых итераций.
Предположим, что диагональные элементы системы (1) не равны 0 (аij 0). Из первого уравнения выражаем х1, из второго – х2 и т.д. Из n-ого – хn.
Обозначим
,
(6)
Система (6) приведена к нормальному виду. Запишем ее в матричном виде: X = + x, где
,
,
х0 = – нулевое приближение. Общая формула имеет вид:
Будем решать систему (6) методом последовательных приближений.
хk+1 = хk +
т.е. х0 = ; х(1) = х(0) + ; х(2) = х(1) + …
Теорема 1. Если максимальная сумма модулей коэффициентов при неизвестных в правой части каждого уравнения системы (6) меньше единицы, то последовательность приближений имеет предел.
Если последовательность приближений имеет предел, то
– точное решение системы (6) следовательно, системы (1).
Теорема 2. Необходимым и достаточным условием сходимости метода простых итераций при любом начальном векторе x0 к решению x* системы (6) является требование, чтобы все собственные числа матрицы были по модулю меньше 1.
Условие окончания вычисления.
Пусть
– точное решение системы.
– k-ое приближенное значение неизвестных, вычисленных по методу итераций.
Тогда | xi(k+1) – xi(k) | < для любого i = 1, 2, … , n.
Оценка погрешности:
Определим:
(Норма)
|| || = max {|1|, |2|, …, |n|}
Тогда
max {| x1 – x1(k) |, | x2 – x2(k) |, …, | xn – xn(k) |}
Пример. Показать, что для данной системы итерационный процесс сходится и определить, сколько итераций следует выполнить, чтобы найти неизвестные с точностью = 10–4.
|||| = max {0,42; 0,55; 0,4} 1
|||| = 0,55 – итерационный процесс сходится.