Ответы на вопросы по высшей математике (Вариант 2)

1. Представление чисел в оперативной памяти и связанные с этим погрешности Вся информация, обрабатываемая компьютерами, хранится в ячейках оперативной памяти в двоичном виде. Содержимым любого разряда может быть либо 0, либо 1. Следовательно, использование двоичной системы счисления в качестве внутренней системы представления информации вызвано конструктивными особенностями элементов вычислительных машин. Стандартный размер наименьшей ячейки памяти равен восьми битам, то есть восьми двоичным разрядам. Совокупность из 8 битов является основной единицей представления данных – байт. Для целых неотрицательных чисел используется ячейка памяти 1 байт. Для целых чисел со знаком отводится две ячейки памяти( 16 бит), а для хранения больших целых чисел со знаком отводятся 4 ячейки памяти (32 бита). Старший ( левый) разряд отводится под знак числа. Если число положительное, то в знаковый разряд запишется 0, если число отрицательное, то в знаковый разряд запишется 1 Целые числа – это простейшие числовые типы данных, с которыми оперирует компьютер. Для представления целых чисел используются специально для них предназначенные типы данных. Специальные типы для целых чисел вводятся для: эффективного расходования памяти; повышения быстродействия; введения операции деления нацело с остатком вместо приводящего к потере точности обычного деления вещественных чисел. В подавляющем большинстве задач, решаемых с помощью ЭВМ, многие действия сводятся к операциям над целыми числами. Сюда относятся задачи экономического характера, при решении которых данными служат количества акций, сотрудников, деталей, транспортных средств и т.д. Целые числа используются для обозначения даты и времени, и для нумерации различных объектов: элементов массивов, записей в базах данных, машинных адресов и т.д. Относительная погрешность представления чисел с плавающей точкой («машинное эпсилон») определяется как наименьшее положительное число ε, при сложении которого с единицей получается отличное от единицы число. Это значение зависит от количества знаков, которые можно записать в мантиссе числа. Абсолютная погрешность говорит о том, на сколько полученный результат отличается от истинного результата.

2. Обусловленность задач. Устойчивость и сходимость алгоритмов

Вычислительная математика отличается от других математических дисциплин и обладает специфическими особенностями. Вычислительная математика имеет дело не только с непрерывными, но и с дискретными объектами. Так, вместо отрезка прямой часто рассматривается система точек вместо непрерывной функции f(x) — табличная функция , вместо первой производной — ее разностная аппроксимация, например, Такие замены, естественно, порождают погрешности метода. В машинных вычислениях присутствуют числа с ограниченным количеством знаков после запятой из-за конечности длины мантиссы при представлении действительного числа в памяти ЭВМ. Другими словами, в вычислениях присутствует машинная погрешность (округления) Это приводит к вычислительным эффектам, неизвестным, например, в классической теории обыкновенных дифференциальных уравнений, уравнений математической физики или в математическом анализе. В вычислительной практике большое значение имеет обусловленность задачи, т.е. чувствительность ее решения к малым изменениям входных данных. В отличие от «классической» математики выбор вычислительного алгоритма влияет на результаты вычислений. Существенная черта численного метода — экономичность вычислительного алгоритма, т.е. минимизация числа элементарных операций при выполнении его на ЭВМ. Погрешности при численном решении задач делятся на две категории — неустранимые и устранимые. К первым относят погрешности, связанные с построением математической модели объекта и приближенным заданием входных данных, ко вторым — погрешности метода решения задачи и ошибки округления, которые являются источниками малых возмущений, вносимых в решение задачи. Устойчивость. Чувствительность задачи к неустранимым погрешностям в исходных данных характеризуется устойчивостью. Пусть в результате решения задачи по исходному значению величины x находится значение исходной величины y. Задача называется устойчивой по исходному параметру x, если решение y непрерывно от него зависит, т.е. малое приращение исходной величины приводит к малому приращению искомой величины . Другими словами, малые погрешности в исходной величине приводят к малым погрешностям в результате расчетов. Сходимость означает близость получаемого численного решения задачи к истинному решению задачи. Ограничимся лишь двумя понятиями сходимости.

3. Прямые методы для решения систем линейных уравнений. Метод Гаусса, Крайта-Халецки, метод прогонки

Прямые методы используют конечные соотношения (формулы) для вычисления неизвестных. Они дают решение после выполнения заранее известного числа операций. Они сравнительно просты и наиболее универсальны (т.е. пригодны для решения широкого класса линейных систем). Недостатки прямых методов: — необходимость хранения в оперативной памяти компьютера сразу всей матрицы (при большой размерности матрицы требуется большого места в памяти); — накапливание погрешностей в процессе решения; это особенно опасно для больших систем, а также для плохо обусловленных систем, весьма чувствительных к погрешностям (в связи с этим прямые методы используют обычно для не слишком больших (n<=1000) систем с плотно заполненной матрицей и не близким к нулю определителем). Метод Гаусса основан на приведении матрицы системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнения системы. Прямой ход: — с помощью первого уравнения исключается x1 из всех последующих уравнений системы; — с помощью второго уравнения исключается x2 из третьего и всех последующих уравнений, преобразованных на предыдущем шаге. Этот процесс продолжается до тех пор, пока в левой части последнего (n-го) уравнения не останется лишь один член с неизвестным xn, т.е. матрица системы будет приведена к треугольному виду. Обратный ход — последовательное вычисление искомых неизвестных: — решая последнее уравнение, находим единственное в этом уравнении неизвестное xn; — используя это значение, из предыдущего уравнения вычисляем xn-1 и т.д. ; — последним найдём x1 из первого уравнения. Метод прогонки является модификацией метода Гаусса для частного случая разрежённых систем – системы уравнений с трёхдиагональной матрицей. Метод прогонки состоит из двух этапов – прямой прогонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в вычислении прогоночных коэффициентов Ai и Bi, с помощью которых каждое неизвестное xi выражается через xi+1. Если матрица системы является симметричной и положительно определенной, то для решения системы применяют метод Холецкого (метод квадратных корней). В основе метода лежит алгоритм специального LU-разложения матрицы A, в результате чего она приводится к виду A= . Если разложение получено, то, как и в методе LU-разложения, решение системы сводится к последовательному решению двух систем с треугольными матрицами: и . Для нахождения коэффициентов матрицы L неизвестные коэффициенты матрицы приравнивают соответствующим элементам матрицы A. Затем последовательно находят требуемые коэффициенты по формулам.

4. Обусловленность матрицы и точность решения системы. Нормы вектора и матрицы. Способы оценки числа обусловленности матрицы

Обусловленность – это внутреннее свойство матрицы A, не зависит от метода решения СЛАУ. Матрицы с большим числом обусловленности дают большие ошибки при решении систем. Логарифм числа обусловленности приближенно равен числу значащих цифр, теряемых в решении системы Ax=b. Число обусловленности играет фундаментальную роль в анализе ошибок округления, совершаемых в ходе гауссова исключения. Пусть A и b заданы точно, x* – приближенное решение, полученное методом Гаусса в арифметике с плавающей точкой. Основной результат в исследовании ошибок округления в гауссовом исключении принадлежит Дж.Х.Уилкинсону. Он доказал, что вычисленное решение x* точно удовлетворяет системе (A+DA)x* = b, где DA – матрица, элементы которой имеют величину порядка ошибок округления в элементах матрица A. Тем самым все ошибки округления могут быть слиты воедино и рассматриваться как единственное возмущение, внесенное в матрицу A в момент записи в память компьютера, само же исключение осуществляется без ошибок. В этом смысле метод Гаусса – лучший алгоритм решения СЛАУ. Контроль качества вычислений может быть осуществлен по вектору невязок только для хорошо обусловленных систем. Нормы матриц и векторов, на которые матрицы действуют должны быть согласованы. Норма матрицы А называется согласованной с нормой вектора х, на который действует матрица А; если выполняется неравенство ∙ , (*) которое называется связью, осуществляющей согласование матрицы А с вектором х.

5. Итерационные методы решения систем линейных уравнений

Итерационные методы – это методы последовательных приближений. В них необходимо задать некоторое приближённое решение – начальное приближение. После этого с помощью некоторого алгоритма проводится один цикл вычислений, называемый итерацией. В результате итерации находят новое приближение. Итерации проводятся до получения решения с требуемой точностью. Преимущества итерационных методов: — требуют хранения в памяти машины не всей матрицы системы, а лишь нескольких векторов с n компонентами; — Погрешности окончательных результатов при использовании итерационных методов не накапливаются, поскольку точность вычислений в каждой итерации определяется результатами предыдущей итерации и практически не зависти от ранее выполненных вычислений. На практике наличие сходимости и достижение требуемой точности обычно определяют приближённо: при малом (с заданной допустимой погрешностью) изменении Х на двух последовательных итерациях, т.е. при малом отличии X(k) от X(k-1), процесс прекращается, и происходит вывод значений неизвестных, полученных на последней итерации.

6. Интерполяция и аппроксимация. Интерполяция по Лагранжу и Ньютону

Интерполяция – способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Интерполяцию функций применяют в случае, когда требуется найти значение функции y(х) при значении аргумента xi, принадлежащего интервалу [x0, …, xn], но не совпадающего по значению ни с одним значением, приведенным в таблице 1. Данная задача, а именно интерполяция функций, часто встречается при ограниченности возможностей при проведении эксперимента. В частности из-за дороговизны и трудоемкости проведения эксперимента размер выборки (x0, x1, x2,…, xn) может быть достаточно мал. Интерполяционный полином Лагранжа обычно применяется в теоретических исследованиях (при доказательстве теорем, аналитическом решении задач и т. п.). Если узлы интерполяции равноотстоящие по величине, так что xi+1–x=h=const, где h – шаг интерполяции, т.е. xi=x0+nh, то интерполяционный многочлен можно записать в форме, предложенной Ньютоном. Интерполяционные полиномы Ньютона удобно использовать, если точка интерполирования находится в начале таблицы – первая интерполяционная формула Ньютона или конце таблицы – вторая формула. Аппроксимация – это замена исходной функции f(x) функцией φ(x) так, чтобы отклонение f(x) от φ(x) в заданной области было наименьшим. Функция φ(x) называется аппроксимирующей.

7. Сплайн-интерполяция

Сплайн (от англ. spline, от [flat] spline — гибкое лекало, гибкая плазовая рейка — полоса металла, используемая для черчения кривых линий) — функция в математике, область определения которой разбита на конечное число отрезков, на каждом из которых она совпадает с некоторым алгебраическим многочленом (полиномом). Максимальная из степеней использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1. В современном понимании сплайны — это решения многоточечных краевых задач сеточными методами.Другими словами сплайн — это кусочно заданная функция, то есть совокупность нескольких функций, каждая из которых задана на каком-то множестве значений аргумента, причём эти множества попарно непересекающиеся.Сплайны имеют многочисленные применения как в математической теории, так и в прикладной математике (в частности, в разнообразных вычислительных программах). В частности, сплайны двух переменных интенсивно используются для задания поверхностей в различных системах компьютерного моделирования. Сплайны двух аргументов называют би-сплайнами (например, бикубический сплайн), которые являются двумерными сплайнами, моделирующими поверхности. Их часто путают с B-сплайнами (базисными сплайнами), которые являются одномерными и в линейной комбинации составляют кривые — каркас для «натягивания» поверхностей. Также из базисных сплайнов возможно составить трёхмерную конструкцию для моделирования объёмных тел. Как следует из определения, для построения сплайна, состоящего из n-1 фрагментов, требуется найти такие значения числовых параметров для каждого фрагмента — полинома степени m, которые обеспечат непрерывность в узлах как самой функции, так и необходимых производных. Так, всего следует определить (n-1)*m параметров. С учётом условия интерполяции и непрерывности первых двух производных определение параметров сводится к решению системы, состоящей из n линейных уравнений. Как правило, значения коэффициентов для отрезков полиномов непосредственно не рассчитываются. Для определения интерполяционного сплайна с непрерывной первой производной достаточно рассчитать значение первой производной в узлах. Способ определения производных в узлах сплайна определяет широкое разнообразие интерполяционных сплайнов. Часто производные определяются не как константы, а как некоторые зависимости от интерполируемой функции и сетки интерполяции. Если значение первой производной в узлах рассчитывать исходя из условия непрерывности второй производной (решая систему, составленную из n линейных уравнений), то сплайн будет иметь две непрерывные производные. Такой способ построения сплайна, как и сам сплайн называют глобальным, поскольку при определении каждого из его коэффициентов учитывается всё множество узлов интерполяции. В других случаях, для определения отдельного коэффициента учитываются только ближайшие узлы интерполяции и такие способы построения, как и сами сплайны, называют локальными. Параметры фрагмента такого сплайна можно определить независимо от других фрагментов.

8. Аппроксимация по методу наименьших квадратов и ее виды

Основная задача аппроксимации — построение приближенной (аппроксимирующей) функции, в целом наиболее близко проходящей около данных точек или около данной непрерывной функции. Такая задача возникает при наличии погрешности в исходных данных (в этом случае нецелесообразно проводить функцию точно через все точки, как в интерполяции) или при желании получить упрощенное математическое описание сложной или неизвестной зависимости. Метод наименьших квадратов (МНК) — математический метод, применяемый для решения различных задач, основанный на минимизации суммы квадратов отклонений некоторых функций от искомых переменных. Он может использоваться для «решения» переопределенных систем уравнений (когда количество уравнений превышает количество неизвестных), для поиска решения в случае обычных (не переопределенных) нелинейных систем уравнений, для аппроксимации точечных значений некоторой функции. МНК является одним из базовых методов регрессионного анализа для оценки неизвестных параметров регрессионных моделей по выборочным данным. Метод базируется на применении в качестве критерия близости суммы квадратов отклонений заданных и расчетных значений. При заданной структуре аппроксимирующей функции (х) необходимо таким образом подобрать параметры этой функции, чтобы получить наименьшее значение критерия близости, т.е. наилучшую аппроксимацию.

9. Аппроксимация в базисе взаимно ортогональных функций. Аппроксимация Фурье, Чебышева, Лежандра , Лаггера

Теория аппроксимации в современном виде основана П.Л.Чебышевым [11]. В настоящее время развивается теория наилучшего приближения функций алгебраическими или тригонометрическими полиномами. Большой вклад в развитие теории полиномов наилучшего приближения внес С.Н.Бернштейн и его ученики [2,3]. Наряду с теоретическими достижениями в этой области получены и хорошие практические результаты. В задачах аналитического приближения функций широко применяются и другие подходы, например, интерполяционные формулы, дающие приближенное выражение функции f(x) посредством интерполяционного многочлена P n(x) (Ньютона, Лагранжа, Лаггера, Фурье) степени n. Во второй половине ХХ-го столетия существенное развитие получило приближение так называемыми сплайн-функциями. Трудности, связанные с использованием рассмотренных методов приближения для аналитического описания значений, полученных в ходе экспериментальных исследований, заключаются в следующем. Измерения всегда производятся с некоторой погрешностью, поэтому для снижения влияния ошибок наблюдения увеличивают их число и соответственно объем получаемых данных. Впервые ортогональные разложения (в частном случае тригонометрических базисов) использовались в работах Гюйгенса, Эйлера и Бернулли. Теория последних, включая вопросы разложения по ним произвольных функций, отвечающих определенным условиям, разработана в трудах Фурье и Вейерштрасса. К настоящему времени разработана теория многих других систем ортогональных многочленов. При этом алгебраические ортогональные многочлены объединяются в две группы: классические ортогональные полиномы непрерывного аргумента и классические ортогональные полиномы дискретного аргумента [4, 13]. Указанные группы базисов объединяются целым рядом общих признаков, которые позволяют удовлетворить сформулированные требования по адаптивной аналитической аппроксимации экспериментальных данных.

10. Аппроксимация Безье. Полиномы Бернштейна. Итерационный алгоритм

Сплайны (кривые) Безье или Кривые Бернштейна-Безье разработаны в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Кастельжо из компании «Ситроен», где применялись для проектирования кузовов автомобилей [1]. Кривая Безье относится к полиномам третьего порядка и уникально определяется четырьмя точками. Обозначим эти точки p0 (начальная), p1, p2 (две управляющие) и p3 (конечная). Обозначенные точки будут иметь координаты: (x0, y0), (x1, y1), (x2, y2) и (x3, y3). Любая кривая Безье уникально определяется этими 8 константами. Их значения зависят от координат четырех точек, задающих кривую. Цель этой задачи – вывести уравнения для расчета восьми констант по заданным координатам четырех точек. Первое допущение для вывода этих уравнений заключается в том, что кривая Безье начинается в точке с координатами (x0, y0) при t = 0. Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. Итерационные алгоритмы используются при реализации итерационных численных методов. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т.е. не будет выполняться основное свойство алгоритма — результативность. Примером такого рода алгоритмов, могут служить алгоритмы и методы приближенного вычисления функций и решения различного рода уравнений. Задача вычисления суммы бесконечного ряда с заданной точностью — метод итерации. Задача вычисления определенных интегралов: метод прямоугольников, метод трапеций, метод Симпсона (парабол).

11. Численное дифференцирование. Конечные разности. Порядок и оценка точности разностной схемы

Численное дифференцирование — совокупность методов вычисления значения производной дискретно заданной функции. В основе численного дифференцирования лежит аппроксимация функции, от которой берется производная, интерполяционным многочленом. Метод конечных разностей — численный метод решения дифференциальных уравнений, основанный на замене производных разностными схемами. Является сеточным методом. Разностная схема — это конечная система алгебраических уравнений, поставленная в соответствие какой-либо дифференциальной задаче, содержащей дифференциальное уравнение и дополнительные условия (например краевые условия и/или начальное распределение). Таким образом, разностные схемы применяются для сведения дифференциальной задачи, имеющей континуальный характер, к конечной системе уравнений, численное решение которых принципиально возможно на вычислительных машинах. Алгебраические уравнения, поставленные в соответствие дифференциальному уравнению, получаются применением разностного метода, что отличает теорию разностных схем от других численных методов решения дифференциальных задач (например проекционных методов, таких как метод Галёркина). Решение разностной схемы называется приближенным решением дифференциальной задачи. Хотя формальное определение не накладывает существенных ограничений на вид алгебраических уравнений, но на практике имеет смысл рассматривать только те схемы, которые каким-либо образом отвечают дифференциальной задаче. Важными понятиями теории разностных схем являются понятия сходимости, аппроксимации, устойчивости, консервативности.

12. Методы Ньютона-Котеса для численного интегрирования.

Методы Ньютона-Котеса — это совокупность техник приближенного интегрирования, основанных на: разбиении отрезка интегрирования на равные промежутки; аппроксимации подинтегральной функции на выбранных промежутках многочленами; нахождении суммарной площади полученных криволинейных трапеций. Одним из простейших методов численного интегрирования является метод прямоугольников. На частичном отрезке подынтегральную функцию заменяют полиномом Лагранжа нулевого порядка, построенным в одной точке. В качестве этой точки можно выбрать середину частичного отрезка . Тогда значение интеграла на частичном отрезке: (2.6) Подставив это выражение в (2.4), получим составную формулу средних прямоугольников: (2.7) Графическая иллюстрация метода средних прямоугольников представлена на рис.2.2(a). Из рисунка видно, что площадь криволинейной трапеции приближенно заменяется площадью многоугольника, составленного из N прямоугольников. Таким образом, вычисление определенного интеграла сводится к нахождению суммы N элементарных прямоугольников. Формулу (2.7) можно представить в ином виде: или (2.8)

13. Квадратурная формула Гаусса

Формулу называют формулой механических квадратур или просто квадратурной формулой, а Sn =Pn k=1 Akf(xk) — квадратурной суммой ; Ak – квадратурными коэффициентами формулы (6); xk – узлами квадратурной формулы. Узлы квадратурной формулы (кратности единица) упорядочены по возрастанию a = x0 < x1 < … < xn = b . Квадратурная формула (6) имеет алгебраическую степень точности m , если она верна для любых многочленов степени m и не верна для многочленов степени m+1 . Квадратурная формула Гаусса характеризуется тем, что коэффициенты Ak и узлы xk выбираются таким образом, чтобы квадратурная формула (6) была точна для всех алгебраических многочленов степени 2n−1 (точна для степеней x от нулевой до 2n−1 ): Zb a p(x)xm dx = n X k=1 Akxm k , m = 0,1,…,2n−1. Для того, чтобы квадратурная формула (6) была точной для алгебраических многочленов степени 2n−1, необходимо и достаточно выполнение условий: формула должна быть интерполяционной; узлы xi формулы (6) должны быть такими, чтобы узловой многочлен ω() = (x−x1)(x−x2)…(x−xn) = xn +an−1xn−1 +an−2xn−2 +…+a0 был ортогонален с весом p(x) ко всякому многочлену Q(x) степени меньше n. При этом корни многочлена ω(x) все лежат внутри [a,b] и различны между собой; коэффициенты квадратурной формулы Ak > 0, k = 1,n, квадратурная формула типа Гаусса не может быть верной для всех многочленов степени 2n.

14. Методы решения нелинейных уравнений. Методы бисекции и «золотого сечения», секущих хорд и парабол

Методы решения нелинейных уравнений: • прямые • итерационные Прямые методы позволяют записать корни уравнения в виде формулы. Например, корни квадратного уравнения ax2 + bx + c = 0 записываются по формуле: ?1,2 = −?± ?2−4?? 2? . На практике уравнения не всегда можно решить прямыми методами. Для их решения применяются итерационные методы, т.е. методы последовательных приближений. Решение нелинейных уравнений итерационными методами проводится в 2 этапа: 1. Отделение корней, т.е. установление малых отрезков, в каждом из которых содержится только один корень уравнения. 2. Уточнение корней до некоторой заданной степени точности. Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях. Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.

15. Метод Ньютона, метод простых итераций для решения нелинейного уравнения. Оценка сходимости метода

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить ноль первой производной либо градиента в случае многомерного пространства. Сходимость метода Ньютона устанавливает следующая теорема. Теорема. Пусть – простой корень уравнения и в некоторой окрестности этого корня функция дважды непрерывно дифференцируема. Тогда найдется такая малая – окрестность корня , что при произвольном выборе начального приближения из этой окрестности итерационная последовательность, определенная по формуле не выходит за пределы этой окрестности и справедлива оценка. Сходимость метода Ньютона зависит от того, насколько близко к корню выбрано начальное приближение.

16. Методы решения системы нелинейных уравнений. Метод Ньютона и метод простых итераций

Классический метод Ньютона или касательных заключается в том, что если — некоторое приближение к корню уравнения , то следующее приближение определяется как корень касательной к функции , проведенной в точке . Уравнение касательной к функции в точке имеет вид: В уравнении касательной положим и . Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем: Сходимость метода касательных квадратичная, порядок сходимости равен 2. Таким образом, сходимость метода касательных Ньютона очень быстрая. Запомните этот замечательный факт! Без всяких изменений метод обобщается на комплексный случай. Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным. Упражнение 1. Найти с помощью метода касательных решение уравнения на отрезке (0, 2). Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3). К недостаткам метода Ньютона следует отнести его локальность, поскольку он гарантированно сходится при произвольном стартовом приближении только, если везде выполнено условие , в противной ситуации сходимость есть лишь в некоторой окрестности корня. Недостатком метода Ньютона является необходимость вычисления производных на каждом шаге. Метод простых итераций Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки. Пусть и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что). По теореме Банаха существует и единственна неподвижная точка Она может быть найдена как предел простой итерационной процедуры где начальное приближение — произвольная точка промежутка . Если функция дифференцируема, то удобным критерием сжатия является число . Действительно, по теореме Лагранжа Таким образом, если производная меньше единицы, то является сжатием. Условие существенно, ибо если, например, на [0,1] , то неподвижная точка отсутствует, хотя производная равна нулю. Скорость сходимости зависит от величины . Чем меньше , тем быстрее сходимость. Рассмотрим уравнение: . Если в качестве взять функцию , то соответствующая итерационная процедура будет иметь вид: . Как нетрудно убедиться, метод итераций в данном случае расходится при любой начальной точке , не совпадающей с собственно неподвижной точкой . Однако можно в качестве можно взять, например, функцию . Соответствующая итерационная процедура имеет вид: . Эти итерации сходятся к неподвижной точке для любого начального приближения : Действительно, в первом случае , т.е. для выполнения условия необходимо чтобы , но тогда . Таким образом, отображение сжатием не является. Рассмотрим , неподвижная точка та же самая, ситуация другая. Здесь, хотя формально производная может быть довольно большой (при малых ж), однако уже на следующем шаге она будет меньше 1. т.е. такой итерационный процесс всегда сходится. Метод Ньютона представляет собой частный случай метода простых итераций. Здесь нетрудно убедиться, что при существует окрестность корня, в которой то если корень кратности , то в его окрестности и, следовательно,. Если — простой корень, то сходимость метода касательных квадратичная (то есть порядок сходимости равен 2). Поскольку , то откуда Таким образом, сходимость метода Ньютона очень быстрая.