Вычислительная математика

  Преподаватель: Клинаев Юрий Васильевич, д.ф.-м.н., профессор 10.01.2022 бЗ-ИВЧТипу -31 Д-362 09:45-11:15 лекция Вычислительная математика Д-356 11:30-13:00 лекция Вычислительная математика (Методы) № почта 1. Алимов Александр Дмитриевич [email protected] 2. Афонин Андрей [email protected] 3. Белинин Владислав Олегович [email protected] 4. Буслаева Алина Игоревна [email protected] 5. Глухов Кирилл Игоревич  [email protected] 6. Грачёв Денис Дмитриевич [email protected] 7. Гуляев Руслан Азадович 89085403354 8. Долгов Ярослав Владимирович [email protected] 9. Ефремов Никита Дмитриевич  [email protected] 10. Жигачев Дмитрий Алексеевич [email protected] 11. Кадушкин Андрей Вячеславович [email protected] 12. Кениг Артём Владимирович  [email protected] 13. Кудряшов Артём Владимирович [email protected] 14. Куку Владислав Сергеевич [email protected] 15. Макян Артур Сагателович [email protected] 16. Никифоров Владислав Витальевич [email protected] 17. Потапов Владислав Евгеньевич [email protected] 18. Сафонов Евгений Константинович [email protected] 19. Титов Артем Геннадьевич [email protected] 20. Хачатуров Давид Каренович [email protected] Лекция 1(конспект) Вычислительная математика Концепция итерационных вычислений в вычислительной математике на примере: Решение алгебраических и трансцендентных уравнений В практике вычислений приходится решать уравнения вида f(x) = 0, где f(x) определена на некотором конечном или бесконечном интервале (a, b). Если f(x) — многочлен, то f(x) =0 — алгебраическое уравнение, иначе f(x) = 0 — трансцендентное уравнение. Всякое значение x* такое, что f(x*) 0, называется корнем, а способ нахождения этого x* и есть решение уравнения. Этапы решения: 1. Отделение корней, то есть отыскание достаточно малых областей, в каждой из которых заключен один и только один корень уравнения. 2. Вычисление корней с заданной точностью. Комментарий 1. Для выделения областей, в которых находятся действительные корни уравнения, можно воспользоваться тем, что если на концах отрезка непрерывная функция f(x) принимает значение разных знаков, то на этом отрезке f(x) = 0 имеет хотя бы один корень. Для выделения областей, содержащих один и только один корень можно воспользоваться, например, графическим способом. Комментарий 2. Для решения 2-й задачи существуют многочисленные методы: метод итераций, метод Ньютона, метод половинного деления и т.д. Считаем, что нам известен отрезок , внутри которого существует и располагается один и только один из корней уравнения. Уравнение f(x) =0 представим в виде x = ,то есть f(x) = x- = 0. В общем случае: , то есть или , где = const. Выберем на отрезке произвольную точку x0 — нулевое приближение, а далее в качестве следующего приближения: x1=, x2=, … xn=. Процесс последовательного вычисления чисел xn (n=1, 2, …) по формуле xn=называется методом итераций. Если на , содержащем корень x = x* , а так же его последовательные приближения x0, x1,…,xn, вычислимые по методу итераций, выполнено условие , то процесс итераций сходится, то есть увеличивая n, можно получить приближение, сколь угодно мало отличающееся от истинного значения корня x*. Процесс итераций следует продолжать до тех пор, пока для 2-х последовательных приближений xn-1 и xn не будет обеспечено выполнение неравенства , где — заданная погрешность Если g0.5, то и можно ограничиться . Итак, ||<1 : — докажем сходимость. Действительно : пусть x* — корень, то есть x* = — с одной стороны, xn = — схема итераций. xn-x* = xn-x* = Используем теорему о среднем значении: если непрерывна на [], то существует точка а, такая, что , где а. Или . Пусть m = max, где x{x0, x1, x2, …, xn} | xn-x* |m| xn-1-x* | | xn-1-x* |m| xn-2-x* | | xn--x* |m2| xn-2-x* | | xn-x* |mk| xn-k-x* | Если k = n, то | xn--x* |mn| x0-x* | Если m<1, то с ростом n: xnx* При ||>1 |xn – x*| неограниченно растет! расходится сходится сходится расходится Для приведения уравнения к виду x = существует следующий способ: Пусть 00 Пример: (извлечение корня степени N из числа A) ; ; ; N = 2; N = 3; Или Лекция 2 (конспект) Вычислительная математика (Методы) (для нелинейных алгебраических и трансцендентных уравнений) Усовершенствованный метод последовательный приближений f(xn-1) = xn; f(xn) = xn+1 ∆x = xn-1 – xn = f(xn) - xn xn+1 = xn + ∆x, лучше взять xn+1 = xn + λ *∆x, λ>1 tg = tg = , где xn f'() = —известно, но можно принять f'( Геометрический процесс отыскания следующего приближения xn-1 сводится к тому, что проводится хорда через точки (xn, f(xn)) и (xn-1, f(xn-1)) и определяется точка ее пересечения с прямой y = x. Сходимость: 1) 01 Так как , то в усовершенствованном методе знаки поправок изменяются нужным образом. 4) f'(x)<-1 0< — расходится, так как поправки велики Каждая поправка умножается на коэффициент между 0 и и процесс расходится. Описанная модификация метода итераций принадлежит Векштейну (1958 г) Метод Ньютона – Рафсона Пусть xn и Если , то метод сходится: Так как f (x) = x, (F (x) = 0 = x – f (x)), то для x, близких к «a», (f (x) - x) – мало. Поэтому (1) сходится, если: 1) выбрано близко к решению x = f (x) 2) f ''(x) – не становится слишком большой. 3) f ' (x) не слишком близка к 1. Это и есть знаменитый метод Ньютона – Рафсона. F (x) = x – f (x) = 0 Или: 1) близко к корню F (x) = 0 2) - не слишком большая 3) - не близка к нулю «3)» означает, что никакие два корня не находятся слишком близко один к другому. Геометрическое толкование. а) , то есть равен углу наклона касательной к y = f (x) в точке б) Уравнение касательной: Пусть выбирать так, чтобы Пример: F (x) = sin x – x + 0.15 = 0 на отрезке [0.5; 1] с погрешностью То необходимо найти чтобы Это верно при = 1 на [0.5; 1] Примечание: если , то можно 1) 2) 3) Вычисляем 4) Проверяем и так далее. Случай почти равных корней (Масштаб сильно увеличен: на самом деле х0 очень близок к х1 ) Производная близка к 1 при На основании теоремы о среднем Итерационный процесс осциллирует (колеблется) между до бесконечности, не сходясь ни к одному значению корня. Другими словами – не удаётся отделить эти два корня, так как они расположены слишком близко один к другому. Трудности возникают, так как Мейкон (1963) предложил метод, согласно которому сначала находят значение x, где , то есть решается уравнение: Пусть - решение. Эта точка Положим для начального приближения Пусть Разложим f (x) в ряд Тейлора в окрестности точки Так как Пусть Но по условию Если , так как надо решить уравнение Сначала решаем: Потом ищется: Затем начальные приближения для Если , то это означает что имеет более чем один корень вблизи , тогда сначала решается уравнение , то это означает, что имеет более чем один корень . Метод хорд Каждое значение xn+1 находится как точка пересечения оси абсцисс с хордой, проведенной через точки F(a) и F(b) , причем одна из этих точек фиксируется — та, для которой F(x)·F''(x)>0. Если неподвижен конец хорды x = a, то xn+1 = xn - Если неподвижен конец хорды x = b, то xn+1 = xn - Если |xn+1 - xn|>,то в первом случае считаем b = xn+1, во втором a = xn+1 и повторяем вычисление. При использовании метода хорд полагается, что корень находится на отрезке [a,b]. Метод секущих (графическая иллюстрация) Реализуется алгоритмом, описанным выше, если абсцисса a и b взяты с одной стороны от корня. Необходимость вычисления F'(x) и выбора одной из двух формул затрудняют практическое применение методов хорд и секущих в отдельности. Примечание. Студент выбирает вариант задания по своему № в списке таблицы с электронными адресами. Если номер больше, чем Ваш № в списке, то надо сложить цифры своего двузначного номера и взять задание с полученным таким образом №. ЗАДАНИЯ (для КР и зачёта) I. Отделить корни уравнения графически (используя мастер диаграмм среды Excel 2000) и уточнить один из них методом итераций (используя среду VBA для Excel 2000 и «выше») с точностью до 0,001. Вариант №1 Вариант №2 Вариант №3 Вариант №4 Вариант №5 Вариант №6 Вариант №7 Вариант №8 Вариант №9 Вариант №10 Вариант №11 Вариант №12 Вариант №13 Вариант №14 Вариант №15 Необходимо вычислить приближенное значение корней уравнения с заданной точностью методом итераций и методом Ньютона-Рафсона. Необходимо построить график y(x) для этих уравнений, отделить корни на соответствующих отрезках. N варианта Уравнение Заданная точность ε 1 10-3 2 10-2 3 10-3 4 10-2 5 10-3 6 10-2 7 10-3 8 10-2 9 10-3 10 10-2 11 10-2 12 10-3 13 10-2 14 10-3 15 10-2 16 10-3 17 10-2 18 10-3 Решение систем линейниых (СЛАУ) и нелинейных уравнений (СНАУ) Метод Ньютона - Рафсона для систем нелинейных уравнений Будем искать решение системы нелинейных уравнений . Считая заданными начальные приближения корней (x0, y0), будем искать поправки к ним h и k: или в общем виде . Таким образом, имеем систему: Раскладывая функции в ряд Тейлора, имеем: Уравнения системы содержат члены более высокого порядка малости, чем h и k. Пренебрегая ими, получим систему относительно h1 и k1: Отсюда Тогда и так далее. Пример. Найти корни системы уравнений: Пусть Тогда Получаем и так далее. Метод итерациЙ для систем нелинейных уравнений Пусть дана система уравнений с двумя неизвестными: . Функции и называются итерирующими. Алгоритм решения задается формулами: Если функции F (x, y) и Ф (x, y) непрерывны и последовательности и сходятся, то пределы их являются корнями системы. Исследуем сходимость. Пусть — истинные значения корней системы и известно, что и в прямоугольнике x = a, x = b, y = c, y = d других корней нет. Тогда, если в этом прямоугольнике выполняются неравенства: . Где , то итерационный процесс сходится, причём в качестве нулевого приближения можно брать любую точку прямоугольника. Пример. Рассмотрим точку x0 = 3,4; y0 = 2,2 Приведём систему (различными путями) к виду: Для — процесс расходится. Поэтому, определим x из 2-го уравнения; y — из 1-го: ; За область изоляции корня можно принять прямоугольник 3 < x < 4; 2 < y < 2,5 Процесс сходится, но так как - близко к единице, то скорость сходимости будет небольшой: ЗАДАНИЯ (для КР и зачёта) II. Решить при помощи метода Ньютона–Рафсона системы уравнений, определив точку начального приближения графически: 1) , 2) , 3) , 4) , 5) , 6) , 7) , 8) , 9) , 10) Системы линейных уравнений Метод Простой итерации Пусть дана система n линейных алгебраических уравнений с n неизвестными Перепишем систему уравнений в виде: Обозначим правую часть i-го уравнения через . Без потери общности не обращаем внимание на то, что в правой части i-го уравнения xi не содержится. Тогда: Зададимся начальными приближениями корней системы Тогда: Итерационный процесс продолжается до тех пор, пока все не станут достаточно близки к , где i = 1, 2, 3, …, n, то есть: Лучше сравнивать с E относительные разности: Исследуем сходимость. Пусть , где xi — истинное значение i-го корня. Так как xi — истинное значение корня, то: Кроме того: Поэтому: Иначе: Обозначим наибольшее из через . Тогда . Если взять: то . Так как это справедливо при любых k, то: Откуда . Если A < 1, то или при . Таким образом, условие сходимости , то есть диагональные элементы системы удовлетворяют условию . Пример: Выбор начальных приближений не влияет на условия сходимости, поэтому чаще всего полагают . Метод Зейделя Метод Зейделя является модификацией метода простой итерации. Итак дана система уравнений: . Для вычисления (k + 1)-го приближения в методе итераций мы использовали , где i = 1, 2, …, n, но так как к моменту вычисления уже найдены то возникает идея: при нахождении использовать найденные ранее . В этом и заключается метод Зейделя: для вычисления (k + 1)-го приближения используется не только k-e, но и (k+1)-e приближения: Пример. В случае, если коэффициенты решаемой системы не удовлетворяют условию сходимости, то с помощью линейного комбинирования уравнений исходной системы получают новую, для которой сходимость обеспечивается. Для этого выбирают из системы уравнений такие, модули коэффициентов в которых больше суммы модулей остальных коэффициентов. Выбранные уравнения записывают так, чтобы наибольший по модулю коэффициент оказался диагональным. Уравнение с): - будет 2-е уравнение Уравнение d): - будет 4-е уравнение a) - b): - будет 3-е уравнение, . a) + b) + 2c) + d): - 1-е уравнение, При получении системы уравнений, удовлетворяющей условиям сходимости метода итераций, необходимо, чтобы каждое уравнение исходной системы, не вошедшее в явном виде в новую систему, попало хотя бы в одну из линейных комбинаций. Примеры. Программные реализации некоторых численных методов в среде VB for Applications Sub Метод_Гаусса() Dim m As Integer 'кол-во ур-й СЛАУ или кол-во строк Dim n As Integer 'кол-во столбцов в матрице коэффициентов Dim a(100, 101) As Single 'матрица коэффициентов Dim c(1 To 100) As Single 'матрица для хранения результатов Dim i As Integer 'счетчик цикла Dim l As Integer 'счетчик цикла Dim z As Integer 'счетчик Dim j As Integer 'счетчик цикла Dim d As Integer 'счетчик Dim f As Single 'переменная для хранения эл-ов массива Dim b As Single 'переменная для хранения эл-ов массива Dim x As Single 'вспомогательная переменная Dim p As Integer 'счетчик цикла x = 0 Worksheets(1).Cells(1, 1).Value = "Метод Гаусса" 'выводим пояснения на лист1 Worksheets(1).Cells(2, 1).Value = "Коэффициенты системы" Stop 'останов исп-ся для того, чтобы задать коэффициенты системы m = CInt(InputBox("Введите кол-во ур-й СЛАУ")) 'переменной m присваиваем кол-во ур-й СЛАУ n = m + 1 'коэффициентов будет на 1 больше, чем уравнений СЛАУ Worksheets(1).Cells(m + 3, 1).Value = "Результат:" 'выводим пояснение на лист1 For i = 1 To m 'с листа считываем коэффициенты в массив коэффициентов For j = 1 To n a(i, j) = Worksheets(1).Cells(i + 2, j).Value Next j Next i z = 0 d = 0 1 For i = 1 To (m - z) 'Методом исключения Гаусса преобразуем матрицу коэффициентов СЛАУ b = a(i + z, z + 1) For j = 1 To (n - z) If (d = 0) Then f = a(i + z, j + z) For l = (1 + z) To n a(i + z, l) = a(i + z, l) / f Next l d = d + 1 If z = (m - 1) Then GoTo 3 GoTo 4 Else: a(i + z, j + z) = a(i + z, j + z) - a(z + 1, j + z) * b End If Next j 4 Next i z = z + 1 d = d - 1 GoTo 1 3 For i = m To 1 Step -1 'выведем преобразованную матрицу коэффициентов СЛАУ на лист2 For j = n To 1 Step -1 Worksheets(2).Cells(i, j).Value = a(i, j) Next j Next i c(m) = a(m, n) 'запоминаем найденную переменную в матрицу резудьтата For i = (m - 1) To 1 Step -1 'ищем значения остальных переменных x = a(i, n) For j = (n - 1) To (i + 1) Step -1 x = x - a(i, j) * c(j) Next j 5 c(i) = x 'заносим найденное значение в матрицу результата Next i For i = 1 To m 'выводим корни СЛАУ на лист1 Worksheets(1).Cells(m + 4, i).Value = c(i) Next i End Sub Sub Метод_Простых_итераций() Dim n As Integer 'порядок матрицы системы Dim a(100, 100) As Double 'преобразованная матрица Dim x(100) As Double 'матрица для хранения результатов Dim f(100) As Double 'матрица для хранения результатов Dim b(100) As Double 'столбец свободных членов Dim e As Double 'погрешность Dim i As Integer 'счетчик цикла Dim j As Integer 'счетчик цикла Dim c As Boolean 'Переменная для принятия возвращаемого функцией значения n = CInt(InputBox("Введите порядок матрицы системы")) 'переменной m присваиваем порядок матрицы системы Worksheets(3).Cells(1, 1).Value = "Метод простых итераций" 'выводим пояснения на лист1 Worksheets(3).Cells(2, 1).Value = "Преобразованная матрица" Worksheets(3).Cells(2, n + 2).Value = "Столбец свободных членов" Worksheets(3).Cells(2, n + 6).Value = "Столбец начальных приближений" Worksheets(3).Cells(n + 3, 1).Value = "Результат" Worksheets(3).Cells(n + 3, 3).Value = "Счетчик числа итераций" Stop 'останов исп-ся для того, чтобы задать коэффициенты системы e = CDbl(InputBox("Введите погрешность")) For i = 1 To n 'с листа считываем элементы в матрицу a For j = 1 To n a(i, j) = Worksheets(3).Cells(i + 2, j).Value Next j Next i For j = 1 To n 'с листа считываем элементы в матрицу b b(j) = Worksheets(3).Cells(j + 2, n + 2).Value Next j For j = 1 To n 'с листа считываем элементы(начальные приближения) в матрицу x x(j) = Worksheets(3).Cells(j + 2, n + 6).Value Next j c = Itera(n, a(), b(), x(), f(), e) 'Вызываем ф-ю Itera и возвращаемое значение присваиваем переменной с If (c = False) Then MsgBox ("Условие сходимости не выполняется"): GoTo 1 'Если ф-я вернула False For j = 1 To n 'Выводим решение на лист1 Worksheets(3).Cells(n + 3 + j, 1).Value = x(j) Next j 1 End Sub Function Itera(n As Integer, a() As Double, b() As Double, x() As Double, f() As Double, e As Double) As Boolean Dim i As Integer, j As Integer, p As Integer 'Счетчики цикла Dim s As Double 'Переменная для суммирования элементов уравнения всех, кроме диагонального Dim m As Double 'Переменная для хранения модуля разности между ближайшими приближениями Dim s1 As Double Dim k As Integer ' счетчик числа итерации Dim v As Double 'Переменная для хранения передыдущего приближения k = 0 For i = 1 To n 'Проверяем выполняется ли условие сходимости s = 0 For j = 1 To n If j <> i Then s = s + Abs(a(i, j)) 'Если элемент не диагональный Next j If s >= Abs(a(i, i)) Then Itera = False: GoTo 2 'Если условие сходимости не выполняется Next i Do m = 0 For i = 1 To n 'Просматриваем строки матрицы коэффициентов s1 = 0 For j = 1 To n 'Просматриваем столбцы матрицы коэффициентов s1 = s1 + a(i, j) * x(j) Next j v = x(i) 'Запоминаем приближение f(i) = x(i) - (1 / a(i, i)) * (s1 - b(i)) 'Высчитываем следующее приближение If (Abs(v - f(i)) > m) Then m = Abs(v - f(i)) 'Запоминаем модуль разности ' соседних приближений для сравнения его затем с заданной точностью Next i For p = 1 To n x(p) = f(p) Next p k = p + 1 'Увеличиваем значение счетчика Loop While m >= e 'Продолжаем вычисления пока не достигнута точность Itera = True Worksheets(3).Cells(n + 4, 3).Value = k 'Выводим значение счетчика на лист 2 End Function Sub Метод_Зейделя() Dim n As Integer 'порядок матрицы системы Dim a(100, 100) As Double 'преобразованная матрица Dim x(100) As Double 'матрица для хранения результатов Dim b(100) As Double 'столбец свободных членов Dim e As Double 'погрешность Dim i As Integer 'счетчик цикла Dim j As Integer 'счетчик цикла Dim c As Boolean 'Переменная для принятия возвращаемого функцией значения n = CInt(InputBox("Введите порядок матрицы системы")) 'переменной m присваиваем порядок матрицы системы Worksheets(2).Cells(1, 1).Value = "Метод Зейделя" 'выводим пояснения на лист1 Worksheets(2).Cells(2, 1).Value = "Преобразованная матрица" Worksheets(2).Cells(2, n + 2).Value = "Столбец свободных членов" Worksheets(2).Cells(2, n + 6).Value = "Столбец начальных приближений" Worksheets(2).Cells(n + 3, 1).Value = "Результат" Worksheets(2).Cells(n + 3, 3).Value = "Счетчик числа итераций" Stop 'останов исп-ся для того, чтобы задать коэффициенты системы e = CDbl(InputBox("Введите погрешность")) For i = 1 To n 'с листа считываем элементы в матрицу a For j = 1 To n a(i, j) = Worksheets(2).Cells(i + 2, j).Value Next j Next i For j = 1 To n 'с листа считываем элементы в матрицу b b(j) = Worksheets(2).Cells(j + 2, n + 2).Value Next j For j = 1 To n 'с листа считываем элементы(начальные приближения) в матрицу x x(j) = Worksheets(2).Cells(j + 2, n + 6).Value Next j c = Zeidel(n, a(), b(), x(), e) 'Вызываем ф-ю Zeidel и возвращаемое значение присваиваем переменной с If (c = False) Then MsgBox ("Условие сходимости не выполняется"): GoTo 1 'Если ф-я вернула False For j = 1 To n 'Выводим решение на лист1 Worksheets(2).Cells(n + 3 + j, 1).Value = x(j) Next j 1 End Sub Function Zeidel(n As Integer, a() As Double, b() As Double, x() As Double, e As Double) As Boolean Dim i As Integer, j As Integer 'Счетчики цикла Dim s As Double 'Переменная для суммирования элементов уравнения всех, кроме диагонального Dim m As Double 'Переменная для хранения модуля разности между ближайшими приближениями Dim s1 As Double Dim p As Integer ' счетчик числа итерации Dim v As Double 'Переменная для хранения предыдущего приближения p = 0 For i = 1 To n 'Проверяем выполняется ли условие сходимости s = 0 For j = 1 To n If j <> i Then s = s + Abs(a(i, j)) 'Если элемент не диагональный Next j If s >= Abs(a(i, i)) Then Zeidel = False: GoTo 2 'Если условие сходимости не выполняется Next i Do m = 0 For i = 1 To n 'Просматриваем строки матрицы коэффициентов s1 = 0 For j = 1 To n 'Просматриваем столбцы матрицы коэффициентов s1 = s1 + a(i, j) * x(j) Next j v = x(i) 'Запоминаем приближение x(i) = x(i) - (1 / a(i, i)) * (s1 - b(i)) 'Высчитываем следующее приближение If (Abs(v - x(i)) > m) Then m = Abs(v - x(i)) 'Запоминаем модуль разности ' соседних приближений для сравнения его затем с заданной точностью Next i p = p + 1 'увеличиваем счетчик Loop While m >= e 'Продолжаем вычисления пока не достигнута точность Zeidel = True Worksheets(2).Cells(n + 4, 3).Value = p 'Выводим значение счетчика на лист 2 End Function ЗАДАНИЯ (для КР и зачёта) III. Методом Зейделя решить с точностью 0,001 систему линейных уравнений, приведя ее к виду, удобному для итераций. Программу реализовать в среде VBA MS Excel. Вариант №1 Вариант №2 Вариант №3 Вариант №4 Вариант №5 Вариант №6 Вариант №7 Вариант №8 Вариант №9 Вариант №10 Вариант №11