Программный продукт, осуществляющий решение задач по дисциплине "Численные методы"
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ем табулирование с постоянным шагом, является так называемый метод половинного деления. Пусть уравнение имеет на отрезке [а; b] единственный корень, причем функция F(x) на этом отрезке непрерывна. Разделим отрезок [а; b] пополам точкой с = (а + b)/2. Если (что практически наиболее вероятно), то возможны два случая: F(x) меняет знак либо на отрезке [а; с] (рис. 1. а), либо на отрезке [с; b] (рис. 1. б). Выбирая в каждом случае тот из отрезков, на котором функция меняет знак, и, продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.
Рисунок 1 - К решению уравнения F(x) методом половинного деления:
a - функция F(x) меняет знак на отрезке [a; c]; б - функция F(x) меняет знак на отрезке [c; b]
Метод половинного деления вполне можно использовать как метод решения уравнения с заданной точностью. Действительно, если на каком-то этапе процесса получен отрезок [а; b], содержащий корень, то, приняв приближенно , то получим ошибку, не превышающую значения
(1)
1.2 Уточнение корня уравнения методом касательных (метод Ньютона)
Пусть в . Таким образом, итерационная последовательность строится с помощью рекуррентного соотношения
(n = 0, 1, 2, …).(2)
Вопрос о выборе начального приближения и гарантированной сходимости итераций решается просто, если функция удовлетворяет следующим условиям:
1.является дважды дифференцируемой на отрезке [а; b];
2.обе производные - первая и вторая - не меняют знак на этом отрезке, т.е. функция монотонна и не меняет характера выпуклости; ситуация иллюстрируется одним из вариантов на рис. 2.
В такой ситуации за берется тот конец отрезка [а; b], на котором функция и ее вторая производная имеют одинаковые знаки, т.е. выполняется условие . Очевидно, что это левый конец [а; b] на рис.3, а и г и правый конец [а; b] на рис. 2, б и в.
Допустим в дополнение к сделанным ранее предположениям, что также непрерывна на [а; b]. Докажем, что отображение , соответствующее формуле (2), является сжимающим в некоторой окрестности корня уравнения . Для этого, как показано выше, достаточно, чтобы существовало такое число q (0 < q < 1), чтобы в указанной окрестности имело место неравенство . Вычислим производную
Рисунок 2 - Четыре возможности поведения функции F{x) в окрестности корня:
а - функция F(x) убывает и выпукла; б - функция F{x) убывает и вогнута; в - функция F(x) возрастает и вогнута; г - функция F(x) возрастает и выпукла
Непосредственно в корне имеем
,
поскольку . Далее рассуждаем так: раз непрерывная функция обращается в нуль в некоторой точке, то существует такая окрестность этой точки, в которой , что и требовалось доказать.
Для оценки расстояния от очередного приближения до корня можно использовать как общее соотношение, так и следующий прием. По формуле Лагранжа
.
Отсюда получаем
Напомним, что о точке известно лишь то, что она находится между и , поэтому реальная оценка погрешности возможна с помощью следующего неравенства:
(3)
Эта оценка очень удобна, поскольку , так или иначе, вычисляется по мере нахождения членов рекуррентной последовательности (2).
Можно показать, что если имеет на [а; b] непрерывную вторую производную , то погрешности на и -м шагах связаны неравенством
(4)
Таким образом, вычислительный алгоритм, заданный формулой , имеет квадратичную скорость сходимости.
Рассмотренный метод называется методом касательных потому, что если обратиться к графической иллюстрации (рис. 3), то точка , определяемая по формуле (2) при , есть точка пересечения касательной, проведенной к графику функции
в точке с абсциссой , с осью
абсцисс.
Каждому следующему члену итерационной последовательности (2) соответствует точка пересечения касательной, проведенной к графику функции в точке с абсциссой, определяемой предыдущим членом последовательности, с осью абсцисс.
.3 Метод Гаусса
Суть метода Гаусса состоит в преобразовании системы (6) к равносильной ей системе с треугольной матрицей, из которой затем последовательно (обратным ходом) получаются значения всех неизвестных.
(6)
Сам по себе метод Гаусса относится к точным методам. Это означает, что если точно выполнять все требуемые в нем действия, то будет получено точное решение, поскольку погрешность метода в данном случае равна нулю. Понятно, однако, что из-за вычислительных ошибок (включая ошибки округления, а также возможные ошибки в исходных данных) этот идеал практически недостижим.
Процесс решения разбивается на 2 этапа:
1)Прямой ход (состоит в последовательном исключении неизвестных);
2)Обратный ход (нахождение неизвестных).
.4 Метод Зейделя
Метод Зейделя представляет собой модификацию метода последовательных приближений. В методе Зейделя при вычислении (k+1)-го приближения неизвестного учитываются уже найденные ранее (k+1)-е приближения неизвестных .
Пусть дана линейная система, приведенная к нормальному виду:
(7)
Выбираем произвольно начальные приближения неизвестных и подставляем в первое уравнение системы (7):
;
полученное первое приближение подставляем во второе уравнение системы (7):
;
полученные первые приближения и подставляем в третье уравнение системы (7):
и т.д. Наконец,
.
Аналогично с