Численные методы (стр. 5 )

Если положить , то и получим требуемый вид .

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

2. Пусть уравнение заменили уравнением , для которого. Тогда можно рассмотреть функцию , обратную . Полагая , получаем уравнение, причем для функции имеет место условие:

.

Для последнего уравнения метод простой итерации уже применим.

П р и м е р 3.7. Отрезок является интервалом изоляции корня уравнения . Подобрать функцию так, чтобы итерационный процесс метода простой итерации сходился.

Приведем данное уравнение к виду следующим образом: . Так как , то – произвольная константа, функцию будем искать в виде . Константу подберем так, чтобы выполнялось условие для всех . Найдем : . Вычислим производную функции : , поскольку для всех , то монотонно убывает на отрезке , вычислим значения этой функции на концах интервала : , следовательно:

.

Константу найдем из неравенств , из которых следует , или . Положим , тогда:

.

Убедимся в правильности выбора : вычислим и найдем

Пусть , тогда итерационная формула рассматриваемой задачи имеет вид:

.

Отметим, что от значения параметра зависит скорость сходимости метода простой итерации.

П р и м е р 3.8. Дано уравнение и требуется найти наименьший положительный корень .

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

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

Метод Ньютона является одним из наиболее эффективных и быстро сходящихся методов приближенного решения нелинейных уравнений. Значение его заключается в том, что он позволяет привести решение нелинейных уравнений к решению последовательности линейных задач. Однако необходимо знать достаточно точное начальное приближение решению уравнения . По прежнему сохраняется требование на непрерывность функции . Кроме того, необходимо требование на существование и непрерывность двух первых производных и . Аналитическое выражение для используется в методе Ньютона для решения уравнения . Исходные условия те же. На концах выбранного отрезка должно выполняться условие . Условие единственности решения заменяется более жестким требованием постоянства знака на отрезке . Рассмотрим в точке касательную к кривой , задаваемую уравнением:

.

Найдем точку пересечения касательной с осью абсцисс: .

Далее строим касательную в точке , получаем по аналогичной формуле точку . В результате получится последовательность приближений к , в которой каждое следующее приближение будет находиться по правилу, принадлежащему Ньютону: .

Если производная функции обращается в нуль или меняет знак, то корень уравнения может быть не найден. Удобно пользоваться следующим критерием применимости метода Ньютона. Первая производная на конце отрезка , с которого начинается вычисление, не должна обращаться в нуль или менять знак. Кроме того, все приближения к решению уравнения должны оставаться в пределах отрезка и монотонно сходиться к величине. Следовательно, начальное приближение нужно выбрать на том конце отрезка , где выполняется соотношение: .

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

Разложим в ряд Тейлора функцию в точке :

,

где – некоторая точка отрезка . И, поскольку , можно записать:

.

Вычитая из последнего равенства равенство , получим:

.

Поскольку на отрезке :

,

можно записать:

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

Например, если , , , то .

Если производная вычисляется сложно, то можно вычислить ее только раз в начале итерационного процесса. При этом формула сменится на формулу .

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

3.3. Приложение (о решении алгебраических уравнений)

Уравнение 1-й степени. Если уравнение 1-й степени, то оно имеет вид и решается сразу: .

Уравнение 2-й степени было решено в глубокой древности. Общие правила для его решения находим в IX в. у среднеазиатского ученого Мухаммеда из Хорезма, известного под арабским прозвищем аль-Хорезми (Хорезмиец). В своем алгебраическом труде, носящем название «Книга восстановления и противопоставления», «восстановлением» Мухаммед называет перенос вычитаемого из одной части уравнения в другую, где оно становится слагаемым; «противопоставлением» — собирание неизвестных в одну сторону уравнения, а известных в другую сторону. По-арабски «восстановление» называется «ал-джебр». Отсюда название «алгебраическое уравнение». Уравнение решается просто: переносят с обратным знаком в правую часть и, прибавляя затем к обеим частям , получают: .

Но , следовательно: , откуда и получается хорошо известная из курса элементарной математики формула решения квадратного уравнения: .

Уравнения 3-й и 4-й степени. Совершенно иначе было с уравнениями выше 2-й степени. Уже уравнение 3-й степени потребовало совершенно не очевидных соображений и не поддавалось всем усилиям математиков древности. Оно было решено лишь в начале 1500-х годов, в эпоху Возрождения в Италии итальянским математиком Сципио дель Ферро (1465–1526). Ферро своего открытия, по обычаю того времени, не опубликовал, но сообщил одному из своих учеников. Уже после смерти Ферро ученик этот вызвал на соревнование одного из крупнейших итальянских математиков – Тарталья – и предложил ему для решения ряд уравнений 3-й степени. Тарталья (1500–1557) вызов принял и за 8 дней до состязания нашел способ решить любое уравнение вида . За два часа он решил все задачи противника. Профессор математики и физики в Милане Кардан (1501–1576), узнав об открытии Тарталья, начал умолять Тарталья сообщить ему свою тайну. Тарталья, в конце концов, согласился, но с условием, чтобы Кардан хранил его способ в глубоком секрете. Кардан нарушил обещание и опубликовал результат Тарталья в своем сочинении «Великое искусство» («Ars magna», т. е. великое искусство вычислять); формула для решения кубического уравнения с тех пор называется формулой Кардана, хотя ее по справедливости надо было бы назвать формулой Тарталья. Приведем вид одного из решений уравнения , так называемую формулу Кардана:

Вскоре после решения кубического уравнения было решено учеником Кардана Феррари (1522–1565) и общее уравнение 4-й степени. При этом если для решения уравнения 3-й степени понадобилось предварительное решение вспомогательного квадратного уравнения, то решение уравнения 4-й степени опирается на предварительное решение некоторого вспомогательного кубического уравнения. Не будем приводить формулу Феррари, так как она очень громоздка, и ей трудно пользоваться в практических расчетах

Уравнения 5-й и 6-й и высших степеней. Успех итальянских математиков произвел очень большое впечатление. То был первый случай, когда наука нового времени превзошла достижения древних. До того, в течение средних веков, ставили себе целью хотя бы понять сочинения древних, а тут, наконец, решили вопросы, которых древним решить не удалось. И это было в 1500-х годах, т. е. за столетие до изобретения новых исчислений: аналитической геометрии, дифференциального и интегрального, которые окончательно утвердили превосходство новой науки над старой. Не было после этого крупного математика, который не пытался бы продолжить достижения итальянцев и аналогично решить в радикалах[18] уравнения 5-й, 6-й и высших степеней.

Выдающемуся алгебраисту XVII в. Чирнгаузену (1651–1708) даже показалось, что он, наконец, нашел общий метод решения. Метод его был основан на преобразовании уравнения к более простому, но это преобразование само требовало решения некоторых вспомогательных уравнений. Впоследствии, при более глубоком рассмотрении, оказалось, что метод преобразований Чирнгаузена действительно дает решение уравнений 2-й, 3-й и 4-й степени, но уже для уравнения 5-й степени требует предварительного решения вспомогательного уравнения 6-й степени, которое в свою очередь неизвестно как решать.

Знаменитый французский математик Лагранж (1736–1813) в большой работе (имеющей более 200 страниц) «Размышления о решении уравнений в радикалах» критически рассмотрел все известные способы для решения уравнений 2-й, 3-й и 4-й степени и показал, что успех в их решении был основан всегда на обстоятельствах, которые для уравнений 5-й и высших степеней уже не имеют места. Со времени Ферро до этой работы Лагранжа прошло более двух с половиной столетий, и никто за этот длинный промежуток времени не сомневался в возможности решить уравнение 5-й и высших степеней в радикалах, т. е. в возможности найти формулы, содержащие действия сложения, вычитания, умножения, деления и извлечения корней с целыми положительными показателями, которые выражали бы корни уравнения через его коэффициенты, — формулы, подобные тем, при помощи которых в древности было решено квадратное уравнение и в 1500-х годах были решены итальянцами уравнения 3-й и 4-й степени. Считалось, что только никак не удается найти верный и, по-видимому, глубоко скрытый путь к этому решению. Этот вопрос, как выразился Лагранж, «был как бы вызовом человеческому уму».

Открытие Абеля. Каково же было удивление всех математиков, когда в 1824 г. появилась в печати работа молодого норвежца Абеля (1802–1829), в которой дано доказательство того, что если коэффициенты , , …, уравнения считать просто буквами, то не существует никакого радикального выражения, составленного из этих коэффициентов, которое было бы корнем соответствующего уравнения, если степень его . Итак, за три столетия усилия величайших математиков всех стран решить в радикалах уравнение 5-й степени или высшей степени потому не увенчались успехом, что эта задача просто не имеет решения.

Теорема Штурма. Ряд важных для практики вопросов связан с такой задачей: не решая уравнения, получить те или иные сведения относительно расположения его корней. Первым таким вопросом был вопрос об определении числа действительных корней уравнения. То есть, если задано уравнение с действительными коэффициентами, то, не решая его по какому-нибудь признаку, зависящему от его коэффициентов, сказать, имеет ли оно действительные корни; а если имеет, то сколько; или сколько оно имеет действительных корней, лежащих между заданными пределами и . В 1835 г. французский математик Штурм (1803–1855) предложил способ, дающий решение этих вопросов.

Вывод способа Штурма не сложен, но он таков, что можно было еще долго его искать и все же не найти. Сам Штурм был так благодарен судьбе, которая дала возможность именно ему решить эту задачу, знаменитую и чрезвычайно важную для практики, что когда он в своем курсе лекций доходил до изложения своего результата, он обычно говорил: «Вот теорема, имя которой я ношу».

Пусть — многочлен с действительными коэффициентами; — его производная . Поделим многочлен на , обозначив через остаток при этом делении, взятый с противоположным знаком. Далее, поделив на , обозначив остаток, взятый с противоположным знаком через и т. д.

Можно доказать, что последний, отличный от нуля, многочлен построенной последовательности будет некоторым постоянным числом .

Теорема Штурма состоит в том, что если два действительных числа, не являющихся корнями многочлена , то, подставив в многочлены , , …, , и получим два ряда действительных чисел:

, , …, , ,

, , …, , ,

такие, что число перемен знаков в ряде , , …, , больше или равно числу перемен знаков в ряде , , …, , и разность между этими числами перемен знаков в точности равна числу действительных корней , лежащих между и , или, как говорят, что их число равно потере перемен знаков в ряде ,, …, , при переходе от к .

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

Тема 4. Численные методы вычисления определенного интеграла

При решении многих задач, встречающихся в геометрии, экономике, технике, приходится вычислять определенные интегралы.

Пусть требуется вычислить определенный интеграл . Если для подынтегральной функции найдена первообразная , то интеграл, как известно из курса высшей математики, можно вычислить по формуле Ньютона–Лейбница[19]:

.

Однако на практике часто не бывает возможности использовать эту формулу, например, в следующих случаях:

1) если первообразная функция не выражается в конечном виде через элементарные функции. Это относится, например, к известному из теории вероятностей и математической статистики интегралу Гаусса[20]:

2) если аналитическое выражение первообразной функции является настолько сложным, что применение формулы Ньютона–Лейбница становится затруднительным;

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

Во всех этих случаях возникает необходимость разработки методов, позволяющих вычислять приближенные значения интегралов без применения формулы Ньютона–Лейбница. В настоящее время известно много формул приближенного интегрирования, называемых также квадратурными[21] формулами.

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

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

4.1. Формула прямоугольников

Определенный интеграл есть число, равное площади фигуры, ограниченной осью кривой и прямыми и .

Вывод формулы прямоугольников основан на замене определенного интеграла интегральной суммой. Из курса высшей математики известно, что ,

где – интегральная сумма для функции на отрезке .

Разобьем интервал интегрирования на равных частей точками , , где , , , . Число называется шагом квадратурной формулы. Очевидно, что .

При этом получаем: .

Если в качестве взять левые концы частичных отрезков : (), то