Читать онлайн «Численные методы 2. Решение уравнений»

САНКТ ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФИЗИЧЕСКИЙ ФАКУЛЬТЕТ КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ В. А. БУСЛОВ , С. Л. ЯКОВЛЕВ ЧИСЛЕННЫЕ МЕТОДЫ II. РЕШЕНИЕ УРАВНЕНИЙ КУРС ЛЕКЦИИ САНКТ ПЕТЕРБУРГ 2001 Утверждено на заседании кафедры вычислительной физики печатается по решению методической комиссии физического факультета СПбГУ АВТОРЫ: В. А. БУСЛОВ, С. Л. ЯКОВЛЕВ РЕЦЕНЗЕНТ: докт. физ. -мат. наук С. Ю. СЛАВЯНОВ Настоящее издание является второй частью курса лекций по численным методам, читавшихся на про- протяжении ряда лет авторами в первом семестре II курса физического факультета СПбГУ. В пособии принята нумерация формул по главам. Приведенная библиография частично представляет собой источник справочного материала, но, в основном, рассчитана на дальнейшее изучение численных методов. Глава 1 Системы уравнений 1. 1 Решение нелинейных уравнений Задачу нахождения решений уравнений можно формулировать различными способами. Например, как задачу на нахождение корней: /(ж) = 0, или как задачу на нахождение неподвижной точки: F(x) = ж. При этом, в зависимости от формулировки задачи, удобно применять те или иные способы решения. Рассмотрим сначала одномерную ситуацию. 1. 1. 1 Одномерный случай Метод деления пополам Простейшим методом нахождения корней уравнения /(ж) = 0 является метод деления пополам или дихотомия. Предположим, мы нашли две точки жо и х\, такие что /(жо) и f{x\) имеют разные знаки, тогда между этими точками, если / ? С0 , находится хотя бы один корень функции / . Поделим отрезок [жо,Ж!] пополам и введем точку ж2 = X°+Xl. Либо /(ж2)/(ж0) < 0, либо f(x2)f(i) < 0. Оставим ту половину отрезка, для которой значения на концах имеют разные знаки. Теперь этот отрезок делим пополам и оставляем ту его часть, на границах которой функция имеет разные знаки, и так далее, до достижения требуемой точности. К достоинствам метода деления пополам следует отнести его высокую надежность и простоту, при этом от функции требуется только непрерывность. Порядок сходимости метода линейный, на каждом шаге точность возрастает вдвое. Недостатком метода является тот факт, что прежде чем начать его применение, необходимо предвари- предварительно найти две точки, значения функции в которых имеют разные знаки. Очевидно, что метод неприме- неприменим для корней четной кратности. Он также не может быть обобщен на случай комплексных корней и на системы уравнений. Метод простых итераций Пусть F : [а,Ь] —> [а, Ь] и F — сжатие: \F(x) — F(y)\ < q\x — у\ , q < 1 (в частности, тот факт, что F — сжатие, как легко видеть, означает, что F ? С[ад). По теореме Банаха существует и единственна неподвижная точка ж*. Она может быть найдена как предел простой итерационной процедуры ж* = lim хп , ж„+1 = F(xn) , где начальное приближение жо — произвольная точка промежутка [а, Ь]. Если функция F дифференцируема, то удобным критерием сжатия является число q = sup |-Р"(жI = Н-^1с < 1- Действительно, по теореме хЕ[а,Ь] Лагранжа \F(x) - F(y)\ = \F'(O\\x -y\< \\F'\\c\x - у\ = q\x - у\ . Таким образом, если производная меньше единицы, то F является сжатием.