35110

ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

Конспект

Математика и математический анализ

В традиционных областях математическими моделями служат функции производные интегралы дифференциальные уравнения. Значения этой функции при каждом фиксированном x можно получить измерениями или вычислениями. Для запоминания этой функции в памяти компьютера необходимо приближенно описать ее таблицей значений на некотором конечном множестве отдельных точек . Это – простейший пример дискретизации задачи: от задачи запоминания функции на отрезке [0 1] мы перешли к задаче запоминания таблицы значений на дискретном множестве точек из этого...

Русский

2013-09-09

3.33 MB

69 чел.

PAGE  162

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Тульский государственный университет

Кафедра  "Автоматизированные станочные системы"

курс лекций по дисциплине

"ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА"

Тула 2007г.

Содержание

1. Особенности математических вычислений, реализуемых на ЭВМ: теоретические основы численных методов: погрешности вычислений

4

1.1. Дискретизация

7

1.2. Обусловленность

11

1.3. Погрешность

13

1.4. Устойчивость и сложность алгоритма (по памяти, по времени)

20

2. Численные методы линейной алгебры

28

2.1. Основные понятия линейной алгебры. Классификация методов решения

29

2.2. Метод исключения Гаусса. Вычисление определителя и обратной матрицы методом исключения

38

2.3. Численные методы решения линейных уравнений

42

2.3.1. Метод прогонки

42

2.3.2. Итерационные методы

48

3. Решение нелинейных уравнений и систем

57

3.1. Решение нелинейных уравнений

57

3.1.1. Метод половинного деления

61

3.1.2. Метод простой итерации

61

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

66

3.1.4. Метод секущих

71

3.1.5. Метод парабол

72

3.2. Методы решения нелинейных систем уравнений

74

4. Методы приближения и аппроксимации функций

80

4.1. Функция и способы ее задания

80

4.2. Основные понятия теории приближения функций

80

4.3. Интерполяция функций

85

4.3.1 Интерполирование с помощью многочленов

85

4.3.2 Погрешность интерполяционных методов

88

4.3.3 Интерполяционный интеграл Лагранжа

89

4.3.4 Конечные разности

92

4.3.5 Интерполяционные многочлены Стирлинга и Бесселя

95

4.3.6 Интерполяционные многочлены Ньютона

98

4.3.7 Разделенные разности

100

4.3.8 Интерполяционный многочлен Ньютона для произвольной сетки узлов

102

4.3.9 Итерационно-интерполяционный метод Эйткина

104

4.3.10 Интерполирование  с кратными узлами

106

4.4. Равномерное приближение функций

109

5. Численное интегрирование и дифференцирование

113

5.1. Численное дифференцирование

113

5.2. Формулы численного интегрирования

120

5.3. Решение обыкновенных дифференциальных уравнений. Метод конечных разностей для численного решения дифференциальных уравнений

140

5.4. Преобразование Фурье

156

5.4.1 Применения преобразования Фурье

156

5.4.2 Разновидности преобразования Фурье

157

5.4.3 Интерпретация в терминах времени и частоты

160


Лекция № 1

1. Особенности математических вычислений, реализуемых на ЭВМ: теоретические основы численных методов: погрешности вычислений

Современная вычислительная математика ориентирована на использование компьютеров для прикладных расчетов. Любые математические  приложения  начинаются с построения модели явления (изделия, действия, ситуации или другого объекта),  к  которому относится изучаемый вопрос. Классическими примерами математических  моделей  могут служить определенный интеграл, уравнение колебаний маятника, уравнение теплообмена, уравнения упругости, уравнения электромагнитных волн и другие уравнения математической физики. Назовем еще для контраста модель  формальных  рассуждений – алгебру Буля.

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

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

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

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

Заменить приближенной формулой

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

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

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

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

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

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

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

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

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

1.1. Дискретизация

Пусть требуется найти приближенное решение какой-либо задачи, в которой в качестве входных данных участвует какая-либо функция f(x), определенная на всем (бесконечном) множестве точек отрезка 0≤x≤1. Значения этой функции при каждом фиксированном x можно получить измерениями или вычислениями. Для запоминания этой функции в памяти компьютера необходимо приближенно описать ее таблицей значений на некотором конечном множестве отдельных точек . Это – простейший пример дискретизации задачи: от задачи запоминания функции на отрезке [0, 1] мы перешли к задаче запоминания таблицы значений на дискретном множестве точек   из этого отрезка.

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

,

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

  (1.1)

  (1.2)

  (1.3)

Для замены производной  можно воспользоваться формулой

(1.4)

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

Рассмотрим краевую задачу

(1.5)

 y(0) = 2,          y(1) = 3,

Об отыскании функции y(x), определенной на отрезке . Для построения приближенной дискретной модели этой задачи осуществим следующие два шага.

Разобьем отрезок  на  N равных частей длины  каждая, а вместо функции y(x) будем искать набор значений  этой функции в точках . В точках  заменим производную  приближенно по формуле (4) и получим

(1.6)

Кроме того, в силу граничных условий (5) положим

. (1.7)

Система  N+1 линейных уравнений (1.6), (1.7) относительно того же числа неизвестных  является дискретным аналогом задачи (1.5).

Есть основания думать, что с ростом N решение задачи (1.6), (1.7) есть все более точная таблица значений решения задачи (1.5) (в дальнейшем это будет показано).

Обозначим континуальную краевую задачу через , а дискретную краевую задачу (1.6), (1.7) через . Тогда можно сказать, что задаче   мы сопоставили бесконечную последовательность дискретных задач (N=2,3,…).

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

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

Бывает, что из двух, казалось бы, равноценных способов дискретизации  и   один при возрастании  N  дает все более точное приближение к решению континуальной задачи , а другой приводит к “приближенному решению” задачи, которое с ростом N теряет какое-либо сходство с искомым решением.

Задача

Пусть f(x) имеет ограниченные производные до требуемого порядка.

Показать, что погрешности приближенных формул  (1)-(4) суть величины O(h), O(h), , .

1.2. Обусловленность

Во всякой задаче требуется по входным данным сделать заключение о каких-либо свойствах решения. Похожие на первый взгляд задачи могут резко отличаться чувствительностью интересующих свойств решения к возмущению входных данных. Если это чувствительность “мала”, то задача считается хорошо обусловленной; в противном случае – плохо обусловленной. Обычно плохо обусловленные задачи не только предъявляют высокие требования к точности задания входных данных, но и более трудны для вычислений.

Пример. Пусть концентрация y = y(t) некоторого вещества в момент времени t есть функция, удовлетворяющая дифференциальному уравнению

.

Фиксируем произвольно  и делаем приближенное измерение  концентрации , получим

.

Задача состоит в определении концентрации y = y(t) в произвольный момент времени t из отрезка .

Если бы число  было известно точно, то можно было бы указать точную формулу

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

.

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

.

.

Очевидно,

.

Отсюда получаем следующее требование к точности δ измерения y0 :

.

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

Если измерение производить при , то , т. е. достаточно измерение с гораздо меньшей точностью, чем в случае , и задача хорошо обусловлена.

Задачи

  1.  На каком из двух отрезков, x  или [-1, 0], задача вычисления  по x лучше обусловлена.
  2.  Пусть . Можно написать также . Какая из двух формул чувствительнее к погрешности при приближенном задании   в виде конечной десятичной дроби?

Указание.  Сравнить модули производных функций  (x-1) и .

1.3. Погрешность

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

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

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

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

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

Проиллюстрируем эти понятия.

  1.  Неустранимая погрешность. Пусть задача состоит в вычислении значения y некоторой функции y = f(x) при некотором = t. Число t и соответствие f, в силу которого каждому значению аргумента сопоставляется значение функции, служат входными данными задачи, а число y(t) – решением.

Пусть функция f(x) известно лишь приближенно, например, , причем известно лишь, что f(x) отличается от  не более, чем на некоторую величину :

. (1.8)

Пусть значение аргумента x = t получается приближенным измерением, в результате которого получаем некоторое , причем известно лишь, что t лежит в пределах

(1.9)

где  – число, характеризующее точность измерения.

Из рис. 1 видно, что величиной y = f(t) может оказаться любая точка отрезка [a, b], где , . Понятно, что, приняв за приближенное значение числа y = f(t) любую точку  отрезка [a, b], можно гарантировать оценку погрешности

. (1.10)

Рис. 1 – Оценка неустранимой погрешности

Эту оценку погрешности нельзя существенно уменьшить при имеющихся неполных входных данных. Самая малая погрешность, которую можно гарантировать, получается, если принять за  середину отрезка [a, b], положив

.

Из рис. 1 видно, что гарантирована оценка

. (11)

Это неравенство станет точным равенством, если y(t) = a или y(t) = b.

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

Оптимальная оценка (1.11) ненамного лучше оценки (1.10). Поэтому мы отступим от здравого смысла, если о любой точке , а не только о точке , условимся говорить, что она есть приближенное решение задачи вычисления числа y(t), найденное с неустранимой погрешностью, а вместо  из (4) за величину неустранимой погрешности примем (условно) число .

  1.  Погрешность метода. Положим . Число  принадлежит отрезку [a, b] и является неулучшаемым приближенным решением задачи, погрешность которого удовлетворяет оценке (1.3) и неустранима. Точка  выбрана среди других точек отрезка [a, b], потому что она задается удобной для дальнейшей работы формулой.

Для вычисления числа  на компьютере воспользуемся разложением функции  в ряд:

 (1.12)

Для вычисления  можно воспользоваться одним из приближенных выражений

,

,                 (1.13)

 

Выбирая для приближенного вычисления  одну из формул (1.6), мы тем самым выбираем метод вычисления.

Величина  есть погрешность метода вычислений.

Фактически выбранный нами метод вычисления зависит от параметра n и позволяет добиваться, чтобы погрешность метода была меньше любой наперед заданной величины за счет выбора этого параметра.

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

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

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

Задачи*

1. Пусть требуется вычислить значение y = f(x) функции f(x) по неполным входным данным .

Какова неустранимая погрешность, вызванная неполным значением входных данных, в зависимости от  и  :

  1.  ;
  2.  ? 

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

2*. Пусть функция f(t) задана таблицей своих значений в точках . Пусть о функции f(t) известно кроме этой таблице еще, что .

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

Указание. Показать, что наряду с функцией f(t) = 0, имеющей нулевую таблицу, функция  также имеет нулевую таблицу и удовлетворяет условию , при этом .

3. Задана некоторая функция y = f(x), о которой известно, что ее вторая производная по модулю не превосходит единицы.

Показать, что погрешность приближенного равенства

не превосходит величину h.

4.Пусть некоторая функция y = f(x) имеет вторую производную , которая по модулю не превосходит единицы. При каждом x значение f(x) получается приближенным измерением величины f(x) и оказывается равным некоторому числу  Пусть известно лишь, что точность измерения гарантирует справедливость оценки

,

где – число, характеризующее точность измерений. Пусть требуется приближенно вычислить f(x).

а) Как выбрать h, чтобы гарантированная погрешность приближенной формулы

была наименьшей?

б) Показать, что неустранимая погрешность задачи вычисления  при заданных (не вполне определенных) входных данных не меньше .

Указание к б). Обе функции, , , имеют вторые производные, не превосходящие единицы по модулю, и . В то же время

.

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

5. Для запоминания сведений о линейной функции ,, удовлетворяющей неравенствам , имеется шесть занумерованных клеток, в каждую из которых можно записать одну из десяти цифр: 0, 1, …,9.

Какова неустранимая погрешность при восстановлении функции, если эти шесть клеток заполнены одним из указанных здесь способов?

а) В первые три клетки записаны соответствующие первые три цифры, стоящие после запятой в записи  в виде десятичной дроби, а в три оставшиеся клетки – первые три цифры, стоящие после запятой в записи  в виде десятичной дроби.

б) Пусть . В первые три клетки записаны первые три цифры десятичной записи числа k, в четвертую клетку – 0 или 1 в зависимости от знака числа k, а в оставшиеся две клетки записаны первые две цифры после запятой из десятичной записи числа .

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

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

1.4. Устойчивость и сложность алгоритма (по памяти, по времени)

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

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

,

y(0) = 0,     (1.14)

где y(t) – отклонение маятника в момент времени t.

При изучении гармонических колебаний с помощью этой математической модели, т. е. задачи Коши (1.14), некоторую пользу может принести знание физической сущности моделируемого физического объекта. В данной задаче, например, можно предвидеть, что решение носит колебательный (периодический) характер. Однако математическая модель (1.14) после ее построения становится самостоятельным объектом, для изучения которого можно применять любые математические средства, в том числе и те, которые не имеют никакого отношения к физическому происхождению задачи. Это сильно расширяет возможности исследователя. Так, например, значение решения  задачи (1.14) в заданной момент времени t = z, т. е. представление числа  в виде десятичной дроби с заданным числом знаков, можно осуществить с помощью ряда

воспользовавшись его частичной суммой.

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

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

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

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

  1.  Алгоритм   может быть точнее алгоритма  , т. е.

.

Например, будем вычислять  по формуле вида

 (1.15)

Примем за  алгоритм, отвечающий n =1, а за  алгоритм, отвечающий n =2. Очевидно, что

.

2. Алгоритмы обладают одинаковой точностью, но вычисление  требует много больше арифметических действий, чем вычисление .

Пусть, например, требуется найти

 

при х = 0,99. За  примем алгоритм, осуществляющий вычисления прямо по заданной формуле, возводя 0,99 поочередно в степени 1, 2, …, 1023 и складывая. В качестве  примем алгоритм, осуществляющий вычисление по формуле  

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

А именно, вычисляя последовательно  придется проделать 1022 умножения. В то же время при вычислении  требуется всего 10 умножений:

.

3. Алгоритмы обладают одинаковой точностью, но  вычислительно устойчив, а  неустойчив.

Например, для вычисления  с заданной точностью  воспользуемся суммой

 (1.16)

где  выбирается так, чтобы выполнялось неравенство

,

Приняв вычисления этой суммы за алгоритм . Если , то

.

При n = 5, и

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

Пусть ; например, х = 100. Тогда для достижения требуемой точности число n должно удовлетворять неравенству:

из которого для n заведомо выполнено неравенство n > 48. Но при вычислении суммы (16) первые ее члены будут очень большими. Малая относительная погрешность при их вычислении дает большую абсолютную погрешность, и алгоритм  вычислительно неустойчив.

Укажем устойчивый алгоритм . Записываем заданное х в виде , (, l целое). Тогда  

,

Этот алгоритм по устойчивости совпадает с алгоритмом  для .

4. Алгоритм может быть сходящимся или расходящимся.

Пусть требуется вычислить . Воспользуемся рядом

(1.17)

и положим

Получим метод вычисления , зависящий от номера n как от параметра.

Если ,  то , т. е. погрешность алгоритма с ростом n стремится к нулю. Но если x > 1, то ,  так как ряд (1.17) имеет радиус сходимости r =1. В этом случае алгоритм непригоден для вычислений.

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

Задачи

  1.  Предложить алгоритм вычисления , пригодный при
    х > 1.
  2.  Рассмотрим задачу об определении последовательности ,  удовлетворяющей уравнению

,   

и дополнительному условию

.  (1.18)

Предлагаются следующие два алгоритма. Полагаем

,   .

В алгоритме  определяем  () как решение уравнения

, (1.19)

при условии

.  (1.20)

Последовательность  определяем равенствами

, ,  (1.21)

. (1.22)

Число с определяем из условия (1.18). При этом значения   последовательно вычисляем по формулам

,   

,   

Алгоритм  состоит в том, что  определяем как решение системы (1.19), но вместо условия (1.20) используем условие . Последовательность  определяем как решение уравнений (1.21), но вместо условия (1.22) используем .

а) Проверить, что второй алгоритм устойчив, а первый очень неустойчив.

б) Попытаться провести решение на компьютере, используя поочередно оба метода при N = 10, а затем при N = 100.


Лекция № 2

2. Численные методы линейной алгебры

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

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

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

Для системы нелинейных уравнений приведено обобщение методов простой итерации, метода итераций Зейделя и метода Ньютона в приложении к одному нелинейному уравнению.

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

2.1. Основные понятия линейной алгебры. Классификация методов решения

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

Две матрицы к и  размерности  равны друг другу, если для всех i и j.

Сумма двух матриц А и В размерности  есть матрица размерности :

Произведение матрицы А на скаляр α есть матрица размерности :

.

Введем обозначение  Произведение матрицы А размерности  на матрицу В размерности  есть матрица С размерности :

Таким образом, элемент  матрицы С есть сумма произведений i строки матрицы А на соответствующие элементы k-го столбца матрицы В, при этом число столбцов матрицы А должно равняться числу строк матрицы В. Из существования произведения АВ вовсе не следует существование произведения ВА. Для квадратных матриц (m=n) одного порядка существуют матрицы АВ и ВА, но, вообще говоря, .

ОПРЕДЕЛИТЕЛЬ (ДЕТЕРМИНАНТ) квадратной матрицы будем обозначать det A:

.

Определитель квадратной матрицы с  элементами (действительными или комплексными числами )есть сумма n! членов вида

где  – алгебраическое дополнение элемента . Отметим, что (неравенство Адамара).

Важным частным случаем квадратной матрицы является ДИАГОНАЛЬНАЯ МАТРИЦА

При  МАТРИЦА называется ЕДИНИЧНОЙ и обозначается через Е. Другим частным случаем квадратной матрицы является ТРЕХДИАГОНАЛЬНАЯ МАТРИЦА

.

С такими матрицами часто приходится иметь дело при решении дифференциальных уравнений. Матрица называется НИЖНЕЙ ТРЕУГОЛЬНОЙ, если все ее элементы, расположенные выше главной диагонали, равны нулю:

Аналогично определяется ВЕРХНЯЯ ТРЕУГОЛЬНАЯ матрица. Квадратная матрица называется СИММЕТРИЧНОЙ, если ее элементы удовлетворяют соотношению  Если в матрице поменять строки со столбцами, то получим транспонированную матрицу

Квадратная матрица А симметрична, если . 

Обозначим через х вектор-столбец и через  – вектор-строку. Матрица называется ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННОЙ, если .

Матрица  называется КОМПЛЕКСНО СОПРЯЖЕННОЙ с матрицей А, если ее элементы суть комплексно сопряженные с элементами матрицы А. Матрица  называется сопряженной с матрицей А. Если матрица А вещественная, то .

Матрица  называется ОБРАТНОЙ матрице А, если . Необходимым и достаточным условием существования обратной матрицы  является условие . Говорят, что в этом случае матрица А несобственная, или невырожденная.

МИНОРОМ порядка k матрицы А называется определитель k-го порядка, составленный из элементов, которые находятся на пересечении k строк и k столбцов матрицы А. РАНГОМ матрицы А называется число r такое, что все миноры порядка r + 1 и выше равны нулю.

ХАРАКТЕРИСТИЧЕСКИМ УРАВНЕНИЕМ матрицы А называется уравнение

Корни  этого уравнения называются СОБСТВЕННЫМИ ЧИСЛАМИ матрицы А. Левая часть уравнения  называется характеристическим полиномом. СОБСТВЕННЫМ ВЕКТОРОМ матрицы А называется отличный от нуля вектор, удовлетворяющий условию . 

Две квадратные матрицы А и В называются ПОДОБНЫМИ, если , где S - невырожденная матрица и . Подобные матрицы имеют одинаковые характеристические многочлены и, следовательно, одинаковые собственные значения и определители, так как  Собственные векторы матрицы А связаны с собственными векторами матрицы В соотношением х = Ву. Матрица А невырожденная, если все  отличны от 0. Все собственные числа симметричной матрицы действительны.

Действительная матрица называется ОРТОГОНАЛЬНОЙ, если ее транспонированная матрица совпадает с обратной, т. е.  или . Все собственные значения ортогональной матрицы по модулю равны единице. Строки (столбцы) ортогональной матрицы попарно ортогональны, суммы квадратов элементов каждой строки (столбца) ортогональной матрицы равны единице, определитель ортогональной матрицы равен ; если матрица А ортогональна, то и матрица  тоже ортогональна.  

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

,

где U – ортогональная матрица,- диагональная матрица. Из свойств ортогональной матрицы следует, что

 

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

•  при х ,   при х = 0.

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

.

Между разными нормами существует соотношение

где   по аналогии с пространством С. Поэтому из сходимости в одной из норм следует сходимость в остальных.

В пространстве квадратных матриц порядка n наиболее употребительны следующие нормы:

                      

                           

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

Интересна связь между нормами матриц и векторов, на которые матрицы действуют. Норма матрицы называется согласованной с нормой вектора, если Сферическая норма согласована с , а максимальная согласована со всеми рассмотренными выше нормами.

Введем понятие предела векторов и матриц. Рассмотрим последовательность векторов  с компонентами Если существуют пределы , то говорят, что вектор с компонентами  является пределом последовательности матриц. Необходимым и достаточным условием сходимости векторов  к x является условие, при этом . Аналогичное утверждение справедливо для матриц.

Требуется найти решение системы линейных уравнений

Ax = b,  (2.1)

где  – квадратная матрица коэффициентов при неизвестных;  – вектор-столбец неизвестных; – вектор-столбец правых частей системы. С точки зрения классической теории линейных алгебраических систем их решение не вызывает затруднений. По правилу Крамера системы n неизвестными имеет единственное решение, если определитель системы отличен от нуля и значение каждого из неизвестных вычисляется как отношение двух определителей порядка n, т. е.

 j =1, …, n. (2.2)

Здесь  – определитель матрицы, получаемый заменой j-го столбца матрицы А столбцом правых частей. При непосредственном вычислении определителей как алгебраической суммы n! произведений элементов для отыскания решения системы линейных уравнений по правилу Крамера требуется приблизительно  арифметических операций типа умножения. Будет показано, что использование метода исключения Гаусса позволяет уменьшить время, необходимое для решения задачи (2.1), до величины менее одной секунды.

Другое важное обстоятельство, связанное с решением систем линейных алгебраических уравнений, состоит в следующем. С точки зрения теории линейных систем различаются два случая: определитель матрицы системы не равен нулю (), т. е. система уравнений является невырожденной, либо определитель матрицы системы равен нулю (detA = 0), в этом случае система называется вырожденной. Во втором случае система либо не имеет решения (при ), либо имеет неединственное решение (при b = 0). С точки зрения практических вычислений существуют “почти невырожденные системы” – системы, определитель которых близок к нулю, но отличен от нуля (). Небольшие изменения коэффициентов матрицы системы или правых частей системы в “почти невырожденных системах” могут привести к большим погрешностям решения.

Все эти случаи хорошо иллюстрируются на примере решения системы двух линейных уравнений:

На рисунке 2 каждому уравнению соответствует прямая на плоскости , а точка пересечения этих прямых есть решение системы (2.1).

Если det A = 0, то наклоны прямых равны и они либо параллельны, либо совпадают. При  небольшие погрешности в коэффициентах и правых частях могут привести к большим погрешностям в решении, т. е. к неточному определению положения точки пересечения.

Рисунок 2 – Графическая интерпретация решения системы линейных уравнений

Системы такого типа, в которых есть малые погрешности в коэффициентах системы или в правых частях (эти погрешности могут быть, в частности, результатом округлений при вычислениях или записи чисел в память компьютера), называются ПЛОХО ОБУСЛОВЛЕННЫМИ.

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

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

Будут рассмотрены наиболее употребительные прямые и итерационные методы. ПРЯМЫЕ МЕТОДЫ дают решение задачи за конечное (точно определяемое для каждого метода) число операций. Здесь намеренно не употребляется термин “точные методы”, так как из-за ошибок округления при вычислениях с конечным числом знаков решение всегда получается с погрешностями. Причины этого и способы уменьшения влияния ошибок округления будут обсуждены ниже. Из прямых методов будут рассмотрены метод Гаусса, метод Гаусса с выбором главного элемента для системы линейных алгебраических уравнений общего вида и метод прогонки для систем линейных уравнений с трехдиагональной матрицей.

ИТЕРАЦИОННЫЕ МЕТОДЫ дают решение как предел бесконечной последовательности приближенных решений, в которых каждое последующее более точное приближение находится по уже найденному предыдущему решению (или предыдущим решениям). Из итерационных методов решения систем линейных алгебраических уравнений рассмотрены метод простой итерации и метод Зейделя.

2.2. Метод исключения Гаусса. Вычисление определителя и обратной
матрицы методом исключения

Систему уравнений (2.1) представим в виде

 (2.3)

или

             i = 1,…, n.

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

___________

Метод Гаусса можно интерпретировать как метод, в котором первоначально матрица приводится к верхней треугольной форме (прямой ход), а далее – к единичной (обратный ход). Очевидно, что если матрица единичная, то

___________

Пусть матрица система (2.3) – верхняя треугольная, поэтому   при i > j, т. е. все элементы ниже главной диагонали равны нулю. Тогда из последнего уравнения сразу определяем  Подставляя  в предпоследнее уравнение, находим  и т. д. 

Общие формулы имеют вид

                       при k = n  (2.4)

            при k = n – 1, n – 2, …, 1.        

При k > l   коэффициенты .            

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

Запишем общие формулы метода Гаусса. Пусть проведено исключение коэффициентов из (k-1)-го столбца. Тогда останутся уравнения с ненулевыми элементами ниже главной диагонали:

            

Умножим kстроку на число  m > k и вычтем из mстроки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

             k < m.

Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-го столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется ПРЯМЫМ ХОДОМ МЕТОДА ГАУССА. Вычисление неизвестных по формулам (2.4) называют ОБРАТНЫМ ХОДОМ метода.

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

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

Для уменьшения ошибок округления поступают следующим образом. Среди элементов первого столбца  каждой промежуточной матрицы выбирают наибольший по модулю (главной) элемент и путем перестановки i-го строки со строкой, содержащей главный элемент, добиваются того, что главный элемент становится ведущим. Такая модификация метода исключения Гаусса называется методом Гаусса с выбором главного элемента. Случай появления нулевых элементов обходится при этом сам собой.

Для реализации метода требуется примерно  операций типа умножения и  операций типа сложения. Полезно помнить, что оценка числа операций определяется в основном операциями, затрачиваемыми при выполнении прямого хода метода Гаусса. Обратный ход метода Гаусса требует примерно  операций. Следовательно, если требуется решить несколько систем линейных алгебраических уравнений вида Ax=b с одной и той же матрицей и различными правыми частями, то общее число операций при решении  S систем будет оцениваться величиной В этом случае целесообразно реализовать алгоритм метода Гаусса в виде двух подпрограмм: первая подпрограмма должна реализовывать прямой ход алгоритма и получать на выходе верхнюю треугольную матрицу, а вторая подпрограмма должна, используя полученную матрицу, вычислять решение системы для произвольной правой части.


Лекция № 3

2.3. Численные методы решения линейных уравнений

2.3.1. Метод прогонки

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

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

• Приведение трехдиагональной матрицы к верхней треугольной (прямой ход), В случае трехдиагональной матрицы это означает приведение к двухдиагональной, т. е. приведение исходной системы к системе, содержащей по два неизвестных в каждом уравнении, кроме последнего, в котором содержится только одно неизвестное.

• Запись обратного хода в виде , так как преобразованная матрица – двухдиагональная.

•Вывод рекуррентного соотношения для  и  через  и  и получение соотношения для  и .

• Осуществление обратного хода метода прогонки и определение всех неизвестных.

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

 i = 1,2,…, n,  (2.6)

Запись (2.6) представляет собой так называемый КАНОНИЧЕСКИЙ ВИД СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДА ПРОГОНКИ. При этом матрица система (2.6) имеет вид

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

 (2.7)

Если система (2.6) приведена к виду (2.7), то обратный ход метода Гаусса очевиден. Однако использование общих алгоритмов прямого и обратного хода нецелесообразно. Построим эффективную вычислительную схему, которая и составляет суть метода прогонки. Для этого, уменьшив в (2.7) индекс на единицу, запишем

Подставляя  в систему (2.6), получим соотношение

из которого нетрудно получить

 

Сравнивая это соотношение с (2.7), можем записать рекуррентные соотношения

      (2.8)

для вычисления так называемых ПРОГОНОЧНЫХ КОЭФФИЦИЕНТОВ.

Подчеркнем, что последующие значения прогоночных коэффициентов  вычисляются только по известным коэффициентам системы (2.6) и известным предыдущим значениям прогоночных коэффициентов

Для начала прямого хода метода прогонки необходимо задать начальные (стартовые) значения прогоночных коэффициентов, например, Отметим, что, вообще говоря, начальные значения коэффициентов  в рассмотренной схеме вычислений не требуются, так как значения коэффициентов вычисляются только через коэффициенты первого уравнения системы (2.6): при i = 1 из (2.6) получаем соотношение  Сравнивая это выражение с (2.7) при i =1, получаем   а значение  в обратном ходе вычисляем по соотношению  Использование  в качестве начальных значений целесообразно по двум причинам: сохраняется однородность вычислительного алгоритма для всех i = 2, 3, …,n; упрощается обсуждение и доказательство условия корректности и устойчивости метода прогонки. Из того обстоятельства, что коэффициенты   не зависят от  (в соотношениях(2.8) при i =1 коэффициенты  умножаются на ), следует, что можно задать любые значения для прогоночных коэффициентов  Далее будет ясно, почему удобно положить  Для начала обратного хода метода прогонки необходимо для вычисления  задать значение . Так как , то из первого соотношения (2.8) вытекает, что  и, следовательно, можно задать любое значение для  Обычно полагают , и тогда

Метод прогонки устойчив, если  Метод прогонки корректен, если

Отметим, что при устойчивости метода прогонки ошибки округления не возрастают, а подавляются. Пусть  - вычисленные с погрешностями значения решения. Пусть при этом коэффициенты  вычисляются точно. Тогда по (2.7)

или

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

Достаточным условием корректности метода прогонки и устойчивости его к погрешностям является условие преобладания диагональных коэффициентов:

         i = 1,2, …, n.

В самом деле, если хотя бы для одного значения i выполняется строгое неравенство , то можно записать цепочку неравенств:

.

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

Для реализации метода требуется примерно 8n операций, из которых 3n составляют операции типа умножения и 5n – операции типа сложения. При численном решении дифференциальных уравнений используются различные варианты метода прогонки: метод встречных прогонок, потоковая прогонка, матричная прогонка для систем векторных уравнений. Отметим, что

Метод прогонки обобщается на случай, при котором в системе (2.6) - квадратные матрицы размерности , а - векторы размерности m. Тогда соотношения (2.7) и (2.8) метода прогонки, в которых все действия совершаются уже над матрицами, а не над скалярами, сохраняются, а  в (2.8) является соответствующей обратной матрицей.

Условие устойчивости матричной прогонки выглядит как , а условие корректности и устойчивости имеет вид .


Лекция № 4

2.3.2. Итерационные методы

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

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

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

Метод простой итерации

В методе простой итерации система (2.1) линейных алгебраических уравнений Ax = b приводится к эквивалентной системе вида

.  (2.9)

Решение системы (2.9) и, следовательно, решение исходной системы (2.1) ищется как предел последовательности векторов при :

  k = 0, 1, 2,…, (2.10)

где  - начальное приближение для вектора решения.

Достаточное условие сходимости метода простой итерации определяется следующей теоремой.

ТЕОРЕМА 1.  Если какая-либо норма матрицы , согласованная с рассматриваемой нормой вектора , меньше единицы (), то последовательность  в методе простой итерации сходится к точному решению   системы (2.9) со  скоростью, не меньшей скорости геометрической прогрессии со знаменате лем  при любом начальном приближении .

ДОКАЗАТЕЛЬСТВО. Для доказательства теоремы введем погрешность . Вычитая из соотношения  равенство (2.10), получаем . Переходя к нормам, имеем

Отметим, что неравенство  из предыдущего выражения является условием согласованности нормы матрицы и вектора. Если , то при любом векторе начальной погрешности (или иначе – при любом начальном векторе ) норма погрешности  стремится к нулю не медленнее геометрической прогрессии со знаменателем .

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

,         i =1,2, …, n,

,  j = 1, 2, …, n. (2.11)

Простейшим и распространенным способом приведения системы Ax= b к виду (2.9), удобному для итераций, является выделение диагональных элементов, при этом каждое iуравнение разрешается относительно i-го неизвестного:

,   i = 1, 2, …, n, (2.12)

и метод простой итерации запишется в виде

Матрица  при этом имеет вид

.

Элемент этой матрицы можно записать в виде  где  - символ Кронекера. В этом случае достаточное условие сходимости метода простой итерации может быть сформулировано как условие преобладания диагональных элементов матрицы А, что следует из (2.11) и записи матрицы , т. е.

             i = 1, 2, …, n.

Еще раз подчеркнем, что рассмотренные формы условия сходимости метода итерации являются лишь достаточными. Их выполнение гарантирует сходимость метода, но их невыполнение в общем случае не означает, что метод простой итерации расходится. Необходимым и достаточным условием сходимости метода простой итерации является условие того, что целая часть (где -максимальное по модулю собственное значение матрицы А); это условие редко используется в практике вычислений.

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

ТЕОРЕМА 2. Если какая-либо норма матрицы , согласованная с рассматриваемой нормой вектора х, меньше единицы (), то имеет место следующая оценка погрешности:

 (2.13)

ДОКАЗАТЕЛЬСТВО. Вычтем из равенства  равенство (2.10):

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

Перейдя к нормам, получим

или

Так как по условию теоремы , то

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

ТЕОРЕМА 3. Если какая-либо норма матрица , согласованная с рассматриваемой нормой вектора х, меньше единицы (), то имеет место следующая оценка погрешности:

Сделаем два замечания. Во-первых, соотношение (2.13) может быть записано в виде

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

Погрешности последовательных итераций связаны соотношением

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

Итак, на примере метода простой итерации продемонстрированы три этапа итерационных методов: построение последовательности векторов, порождаемой формулой (1.10); определение условия сходимости по теореме 1 и оценка скорости сходимости с помощью теорем 2 и 3.

Метод Зейделя

В методе простой итерации не используется кажущаяся очевидной возможность улучшения сходимости итерационного процесса – немедленное введение в расчет вновь вычисленных компонент вектора . Эта возможность используется в итерационном методе Зейделя. Итерационный процесс для системы (2.9) выполняется при этом по соотношению

 i = 1, 2, …, n  (2.14)

или для системы (1.1)

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

Отметим, что метод Зейделя сходится, если матрица А положительно определенная и симметричная.

Покажем, что метод итераций Зейделя эквивалентен некоторому методу простой итерации со специальным образом построенной матрицей  и вектором  в соотношении (2.10). Для этого запишем систему (2.14) в виде  где F-верхняя треугольная матрица из коэффициентов матрицы , а  Перепишем систему в виде где E-единичная матрица. Матрица (Е-Н) - нижняя треугольная матрица с диагональными элементами, равными единице. Следовательно, определитель этой матрицы отличен от нуля (равен единице) и она имеет обратную матрицу . Тогда

 

Сопоставляя это соотношение с решением (2.10), можем заключить, что действительно метод итераций Зейделя эквивалентен методу простой итерации в том смысле, что для установления условия и критерия сходимости метода итераций Зейделя можно воспользоваться теоремами, приведенными для метода простой итерации, если положить  Итерационный процесс для системы (2.12) записывают и в более общей форме, а именно

Вводя в итерационный процесс для  значение , которое отсутствует в методе простой итерации и методе Зейделя.

Итерационный процесс при w > 1 называют МЕТОДОМ ВЕРХНЕЙ РЕЛАКСАЦИИ, при w = 1 (метод Зейделя)-методом ПОЛНОЙ РЕЛАКСАЦИИ и при w < 1 - методом НИЖНЕЙ РЕЛАКСАЦИИ.

В простом случае при специально выбранном w можно дать оценку числа операций N, необходимых для достижения заданной точности . В методе простой итерации  методе Зейделя  методе верхней релаксации  Очевидно, что число итераций тем больше, чем больше порядок системы; при этом имеет место квадратичная зависимость в первых двух методах и линейная зависимость в методе верхней релаксации. Очевидно также, что число итераций тем больше, чем меньше .

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

Можно дать наиболее общую запись итерационного процесса для системы (1.1). Имеем

 (2.15)

где  - некоторая матрица, выбираемая для обеспечения быстрой сходимости метода. Во многом она определяется конкретной системой (2.1) и искусством вычислителя. Говорят, что итерационный процесс стационарный, если  и  не зависят от k; в дальнейшем индекс k при B и  опускается. Из (2.15) очевидно, что если итерационный процесс сходится, т. е.  то он сходится к решению системы (2.1).

Пусть матрицы D и L определены следующим образом:

,              

Тогда метод простой итерации есть частный случай процесса(2.15) при B = D и  метод Зейделя – частный случай при B = D + L,  а метод релаксации – частный случай при B = D + wL,

Матрицу  следует выбирать как можно ближе к матрице А, но так, чтобы обращение этой матрицы было более простой задачей(матрица В – треугольная, трехдиагональная и т. д.).

Лекция № 5

3. Решение нелинейных уравнений и систем

3.1. Решение нелинейных уравнений

Пусть имеется нелинейное уравнение

f(x)=0 (3.1)

Требуется найти корни этого уравнения, т. е. те значения х, которые обращают уравнение (3.1) в тождество. В процессе приближенного отыскания корней уравнения (3.1) обычно выделяют два этапа: отделение корня и уточнение корня.

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

В общем случае этап отделения корня уравнения (3.1) не может быть алгоритмизирован. Для некоторых классов уравнений (наиболее известным из которых является класс алгебраических уравнений) разработаны специальные приемы отделения корней, существенно облегчающие такое отделение и позволяющее автоматизировать этот процесс. Некоторые из этих приемов будут приведены при рассмотрении методов решений алгебраических уравнений. Нередко отделение корней нелинейных уравнений выполняется “вручную” с использованием всей возможной информации о функции f(x). В ряде случаев приближенное значение корня может быть определенно из физических соображений, если речь идет о решении нелинейного уравнения, связанного с конкретной прикладной задачей. Успешно применяется графический метод определения действительных корней, обладающей большой  наглядностью и позволяющий  относительно просто устанавливать возможность существования кратных корней. При графическом отделении корней бывает полезным представить уравнение (3.1) в эквивалентном виде  и искать точки пересечения функций  и . Например, для уравнения   вместо построения графика y = f(x) (рис. 3,а) проще построить графики функций  и  (рис.3,б).

Рисунок 3 – Графическое решение уравнения:

а) Пересечение исходной функции и оси абсцисс;

б) Пересечение двух упращенных функций

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

ТЕОРЕМА. Если функция f(x), определяющая уравнение f(x) = 0 , на концах отрезка принимает значения разных знаков, т. е. , то на этом отрезке содержится по крайней мере один корень уравнения. Если же функция f(x) непрерывна и дифференцируема и ее производная сохраняет знак внутри отрезка , то на этом отрезке находится только один корень  уравнения.

В случае, когда на концах интервала функция имеет одинаковые знаки, на этом интервале корни либо отсутствуют, либо их четное число.

Известно, что интервал, на котором расположены корни многочлена n степени  в том числе и комплексные, выражается соотношением

.

Кроме того, по правилу знаков Декарта разность между числом перемен знаков последовательности  и числом положительных корней является либо положительным числом, либо нулем(в случае действительных корней). Это правило распространяется и на отрицательные корни при замене х на –х. Правило Декарта позволяет также оценить число действительных корней на интервале . Для этого обозначим  и применим правило знаков к уравнению

Для отделения корня полезно также использовать теорему Гюа.

ТЕОРЕМА ГЮА. Если все корни алгебраического уравнения  являются действительными числами, то для последовательности коэффициентов  квадрат каждого некрайнего коэффициента больше произведения соседних с ним коэффициентов, т. е. >, k = 1, 2, …, n-1.

ТЕОРЕМА. Если для каких-либо k выполнено неравенство  то многочлен имеет по крайней мере пару комплексных корней.

На втором этапе уточнения при нахождении корня используют два типа метода: ПРЯМЫЕ и ИТЕРАЦИОННЫЕ. В прямых методах корень уравнения может быть найден за конечное, заранее известное число операций. Прямыми методами удается  решить некоторые простейшие алгебраические и тригонометрические уравнения.

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

Основные методы решения нелинейных уравнений и систем являются итерационными, и к их числу принадлежат метод дихотомии(половинного деления), метод простой итерации, метод Ньютона(метод касательных), метод секущих, метод парабол(метод Мюллера), метод Зейделя. Далее эти методы будут рассмотрены.

Важной характеристикой итерационных методов является скорость сходимости процесса. Говорят, что метод имеет nпорядок сходимости, если , где С - постоянная, не зависящая от n. При n = 1 имеет место сходимость первого порядка, или линейная сходимость, а при n= 2 – второго порядка, или квадратичная. Говорят, что метод является одношаговым, если для построения итерационной последовательности нужно вычислить функцию в одной точке, двушаговым – в двух и т. п.

Сравнение различных методов следует проводить по числу операций при реализации одной итерации и по скорости сходимости.

Изложенные методы решения нелинейных уравнений и систем широко используются в численных методах оптимизации.

3.1.1. Метод половинного деления

Пусть действительный корень уравнения f(x) = 0 отделен и функция f(x) непрерывна на интервале [a, b] отделения корня. Построим процесс сужения интервала [a, b] так, чтобы искомый корень всегда находился внутри суженного интервала. Очевидно, что в этом случае погрешность приближенного значения корня не превышает , где  - граничные точки интервала на k итерации. Найдем середину отрезка и вычислим  Составим произведения  и . Из двух половин отрезков выберем тот, в котором произведение является отрицательной величиной, и обозначим новые границы отрезка через Затем новый отрезок разделим пополам, вновь составим аналогичные произведения и выберем тот из отрезков, в котором произведение – величина отрицательная.

Погрешность метода половинного деления, который также называется МЕТОДОМ ДИХОТОМИИ, определяется достаточно очевидным соотношением (которое, впрочем, может быть строго доказано)

которое указывает на скорость сходимости метода: с увеличением k погрешность стремится к нулю не медленнее геометрической прогрессии со знаменателем q = 1/2. Метод дихотомии прост и надежен, всегда сходится, хотя и медленно, устойчив к ошибкам округления. Метод дихотомии, однако, не обращается на системы уравнений.

3.1.2. Метод простой итерации

При использовании метода простой итерации для уточнения корня уравнение f(x) = 0 заменяется эквивалентным уравнением

 (3.2)

Это означает, что из  следует  и наоборот. Привести уравнение (3.1) к уравнению (3.2) можно многими способами, например, положив , где  - непрерывная произвольная знакопостоянная функция.

Геометрически на интервале отделения корня уравнение (3.2) представляется в виде двух пересекающихся линий  и y  = x (рис. 4). Пологая, что известно начальное приближение  для значения корня , построим итерационный процесс

     k = 0, 1, 2, …, (3.3)

изображенный на рис.4 ломаной линией со стрелочками, указывающими направление движения. Для представленного на рис.4 случая взаимного расположения линий y = x и  неограниченное повторение вычислений по соотношению (3.3) позволяет сколь угодно близко подойти к точному значению корня .

Рисунок 4 – Геометрическая интерпретация метода простой итерации

Исследуем сходимость метода. Если  имеет непрерывную производную, то из теоремы Лагранжа о конечном приращении

 (3.4)

следует, что точка  лежит между точками  и . Поэтому если всюду , то отрезки  убывают не медленнее геометрической прогрессии со знаменателем q<1. Действительно, из (3.4), которое можно рассматривать как рекуррентное соотношение, следует, что  и последовательность  сходится при любом нулевом приближении.

Итак, условие

 (3.5)

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

,

то погрешность на каждой итерации уменьшается для любого начального приближения не медленнее членов геометрической прогрессии со знаменателем q.

Четыре случая взаимного расположения линий y = x и  вблизи корня и соответствующие им итерационные процессы показаны на рис. 5, a и 5. б  соответствуют случаю  – процесс итераций сходится. При этом в первом случае  и сходимость носит односторонний характер (рис. 5., а), а во втором  и сходимость носит двусторонний характер (рис. 5. б). Рис. 5, в и 5, г соответствуют случаю  – процесс итерации расходится, при этом имеет место односторонняя и двусторонняя расходимость.

 

Рисунок 5 – Типовые случаи устойчивой и неустойчивой реализации метода простой итерации

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

Рисунок 6 – Частный случай сходимости метода простой итерации

Используя соотношения(3.4) и (3.5), можно записать

где  Из этого соотношения следует, что скорость сходимости метода итерации зависит от величины q: чем меньше q, тем быстрее сходится метод.

Исходное уравнение f(x) = 0 может быть преобразовано к виду  многими способами, и, очевидно, для метода итерации целесообразно брать то уравнение , для которого q имеет наименьшее значение.

Для пояснения рассмотрим классический пример вычисления квадратного корня. Исходное уравнение  преобразуем к виду  тремя способами, приведенными в табл. 1 в первом столбце.

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

Таблица 1. Примеры выбора функции  в методе простой итерации

Поведение

Сходимость метода

при

Не сходится

<1

при

при

Сходится в ограниченном интервале к отрицательному значению корня

при  

Сходится, и очень быстро

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

Вновь рассмотрим уравнение (3.1). Полагая, что погрешность  мала, а функция f(x) имеет непрерывную вторую производную, разложим  в ряд Тейлора:

где . Учитывая, что  и оставляя только линейную часть разложения в ряд (отсюда и другое название метода – МЕТОД ЛИНЕАРИЗАЦИИ), можем записать приближенное, линейное относительно погрешности, уравнение

из которого для погрешности имеем

 (3.6)

Так как использована лишь линейная часть разложения в ряд, то при подстановке (3.6) в соотношение  следующее из соотношения для погрешности, получим вместо  лишь приближенное уточненное значение корня, которое обозначим  Тогда можем записать основное соотношение метода Ньютона в виде

(3.7)

Это соотношение позволяет построить последовательность приближений  к точному значению корня по заданному приближению

Геометрически процесс (3.7) означает замену на каждой итерации кривой y = f(x) на касательную к ней в точке  и определение значения  как координаты точки пересечения касательной и оси абсцисс (рис. 7). С рассмотренной интерпретацией соотношения (3.7) связано еще одно название метода – МЕТОД КАСАТЕЛЬНЫХ.

Рисунок 7 – Геометрическая интерпретация метода Ньютона

Достаточное условие сходимости метода Ньютона получим из соответствующего условия для метода простой итерации. Сопоставляя соотношения (3.2) и (3.7), можно заключить, что метод простой итерации, в котором

Используя условие сходимости метода итераций  и выражение

Нетрудно получить достаточное условие сходимости метода Ньютона в форме

.  (3.8)

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

Для оценки скорости сходимости метода Ньютона запишем соотношение

Далее разложим  в ряд Тейлора:

Подставляя это разложение в предыдущую формулу и учитывая, что , получаем

Из этого соотношения  следует, что метод Ньютона имеет вблизи корня второй порядок сходимости: на каждой итерации ошибка меняется пропорционально квадрату ошибки на предыдущей итерации. Нетрудно видеть, что метод Ньютона является одношаговым. Достоинства метода Ньютона состоят в его квадратичной сходимости, возможности обобщения на случай систем уравнений, а также в том, что он является одношаговым. Однако метод Ньютона расходится в тех областях, где . Кроме того, если функция f(x) задана таблично, то вычисление затруднено.

Указанная трудность устраняется в МЕТОДЕ СЕКУЩИХ (методе хорд).

Существует вариант метода Ньютона с постоянным значением производной; значение производной вычисляется только в начальной точке  (рис. 8), и далее для всех итераций значения производных  полагаются постоянными, равными

Последовательные приближения вычисляются по формуле

Рисунок 8 – Модифицированный метод Ньютона

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

 

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


Лекция № 6

3.1.4. Метод секущих

В методе секущих, иначе называемом МЕТОДЕ ХОРД, приближенное значение производной  в формуле (3.7) определяется по двум последовательным приближениям   и  по соотношению

 (3.9)

что приводит к замене касательной в точке  секущей, проведенной через две точки кривой y = f(x) (рис.9) или, что то же самое, - к аппроксимации функции f(x) на этом интервале линейной функцией.

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

где  .

Рисунок 9 – Геометрическая интерпретация метода секущих

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

3.1.5. Метод парабол

Рассмотренный метод секущих можно интерпретировать как метод, в котором на каждой итерации исходная функция аппроксимируется линейной функцией (секущей), построенной по двум точкам, принадлежащим f(x). Развивая далее идеи аппроксимации, можно для построения итерационных формул использовать информацию о функции в нескольких точках, предшествующих точке  В методе парабол по трем последовательным приближениям  строится многочлен второй степени (парабола), приближающий исходную функцию. Иначе этот метод называют МЕТОДОМ МЮЛЛЕРА или методом КВАДРАТИЧНОЙ ИНТЕРПОЛЯЦИИ. За новое приближение берется обычно ближайший к  корень соответствующего квадратного уравнения. Геометрическая интерпретация метода парабол дана на рис.10.

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

где p = 1,839.

Рисунок 10 – Геометрическая интерпретация метода парабол

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

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


Лекции № 7 – 8

3.2. Методы решения нелинейных систем уравнений

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

Метод простой итерации

Систему нелинейных уравнений запишем в векторной форме

f(x) = 0 (3.10)

где  - вектор-столбец неизвестных,  - вектор-столбец функций. В методе простой итерации система (3.10) приводится к эквивалентной системе вида  где  или

(3.11)

Полагая известным начальное приближение для корня  построим итерационный процесс  или

 (3.12)

Рассмотрим поведение вектора погрешности

полагая, что погрешность – величина малая. Для компонент вектора x можем записать

               

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

,    (3.13)

Из (3.13) следует, что в методе простой итерации вектор погрешности испытывает линейное преобразование, или, иначе, метод имеет первый порядок сходимости.

Если обозначить матрицу производных системы функций  для   (МАТРИЦУ ЯКОБИ) ЧЕРЕЗ

то систему (3.13) можно переписать в виде

 (3.14)

Достаточное условие сходимости итерационного процесса (3.12) формулируется следующим образом: если какая-либо норма матрицы  согласованная с рассматриваемой нормой вектора x, меньше единицы, то метод итераций сходится, Условие сходимости  есть обобщение на случай нелинейной системы условия (3.5) для одного уравнения.

Метод итераций Зейделя

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

     

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

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

Основная идея метода Ньютона – решение системы нелинейных уравнений f(x) = 0 сводится к решению последовательности линейных задач, дающих в пределе решение исходной задачи. Линейная задача получается путем выделения из нелинейных уравнений главной линейной части.

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

    (3.15)

линейную относительно компонент вектора погрешностей. Если использовать эту систему для отыскания компонент вектора погрешностей, то в силу приближенности системы (3.15) – оставлена лишь линейная часть – найденное значение вектора погрешности будет лишь приближенным, Тогда при подстановке полученного решения в соотношение  будет иметь вместо  приближенное уточненное значение корня, которое обозначим через  Используя запись системы (3.15) в виде

 

где  - матрица производных системы функций  (матрица Якоби), можем записать итерационный процесс для нахождения вектора x.

          

где  - матрица, обратная матрице Якоби. Представленная формула является обобщением формулы (3.7) на случай систем нелинейных уравнений. Уточненное значение вектора может быть вновь использовано для получения следующего приближения к корню, что приводит к итерационному процессу. Заметим, что в большинстве случаев предпочтительным является не вычисление обратной матрицы  а получение каким-либо методом решения  линейной системы (3.15) и вычисление нового приближенного значения по соотношению

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

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

Ускорение сходимости по Эйткену

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

Из этого соотношения следует, что

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


Лекция № 9

4. Методы приближения и аппроксимации функций

4.1.Функция и способы ее задания

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

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

Указанные недостатки аналитического способа устраняются в случае графического способа задания функции у = f(x).

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

4.2 Основные понятия теории приближения функций

Теорией и практикой приближения (аппроксимации) функции приходится пользоваться при решении многих практических задач.

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

Другими распространенными примерами аппроксимации функций являются задачи определения производной и интеграла  по заданным значениям .

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

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

В процессе численной реализации этого подхода необходимо рассмотреть следующие четыре основных вопроса:

1. Вопрос об имеющейся информации относительно функции f, т.е. о виде, в котором задана функция f. Различают два основных случая: функция f задана либо аналитически, либо в виде таблицы. Графический способ относят к первому, или ко второму случаю в зависимости от конкретной задачи. В дальнейшем будем рассматривать на отрезке  непрерывные вместе с достаточным количеством своих производных функций f(x), определенные значениями в узлахзаданной сетки .

2. Вопрос о классе аппроксимирующих функций, т.е. какими функциями  будет аппроксимирована функция f. Во-первых, аппроксимирующая функция должна отражать характерные особенности аппроксимируемой, а во-вторых, быть достаточно удобной в обращении, т.е. при выполнении над ней необходимых операций.

В численном анализе широкое применение имеют 3 группы аппроксимирующих функций. Первая – функции вида 1, х, …,, линейные комбинации которых порождают класс всех много членов степени не выше n. Вторую группу образуют тригонометрические функции   и , порождающие ряды Фурье, и интеграл Фурье. Третья группа состоит из экспоненциальных функций , определяющих явления типа распада и накопления, часто встречающихся в реальных ситуациях.

Принимаем в качестве аппроксимирующей функции многочлен некоторой степени n. В этом случае функция имеет вид .

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

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

.

Наибольший интерес представляет частный случай, когда для аппроксимирующей функции расстояние . Это означает, что для табулированной функции y=f(x), заданной значениями  (табл. 2) требуется построить аппроксимирующую функцию , совпадающую в узлах со значениями заданной функции у=f(x), т.е. такую, что .


Таблица 2. Структура табличного задания функции

              ….  

              ….

Такой способ аппроксимации, основанный на критерии совпадения f и  в узлах , называется интерполированием (или интерполяцией). Если аргумент, для которого определяется приближенное значение функции, принадлежит отрезку , то задача вычисления значение функции в точке х называется интерполированием в узком смысле. Если же аргумент х находятся вне отрезка , то поставленная задача называется экстраполированием.

Геометрически задача интерполирование для функции одной переменной y=f(x) означает построение на плоскости Х0У кривой, проходящей через точки с координатами .

Приведем еще один пример критерия согласия. Введем понятие расстояния между функциями f и  как суммы квадратов их отклонений в узловых точках:

.

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

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


Лекция № 10

4.3 Интерполяция функций

4.3.1 Интерполирование с помощью многочленов

Рассмотрим задачу интерполирования функции f с помощью алгебраических многочленов. В этом случае аппроксимирующая функция  имеет вид

. (4.1)

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

В качестве критерия согласия принимается условие совпадения  и f в узловых точках. Для однозначного определения n+1 коэффициентов  многочлена  необходимо потребовать совпадения f и необходимо потребовать совпадения f и в (n+1)-й узловой точке:

  (i = 0,1,…,n) (4.2)

Многочлен , удовлетворяющий условиям (3.2), называется интерполяционным многочленом. Чтобы подчеркнуть зависимость этого многочлена от функции f, его часто обозначают .

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

. (4.3)

В том же случае, когда интерполяция производится на всем отрезке , в качестве погрешности принимается максимальное отклонение многочлена  от функции f на рассматриваемом отрезке:

.

Итак, рассмотрим следующую задачу интерполирования. На сетке  в узлах  заданы значения  (i = 0,1,….,n) функции f. Требуется построить интерполяционный многочлен , совпадающий с f в узлах  заданны значения  (i=0,1,….,n) функции f. Требуется построить интерполяционный многочлен , совпадающий с f в узлах , и оценить погрешность .

Теорема 1. Пусть:

  1.  на отрезке [a,b] заданна сетка ;
  2.  заданны произвольные числа   (i=0,1,…,n).

Тогда существует единственный многочлен  степени не выше n, принимающий в узлах  заданные значения  

Из условий для определения неизвестных коэффициентов  многочлена  получаем систему алгебраических уравнений

 (i=0.1,….,n) (4.4)

Определитель этой системы

(4.5)

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

Коэффициенты  интерполяционного многочлена (4.1) можно определить, положив в системе (4.4)  и решив ее, например, по формуле Крамера:

.

Здесь  - определитель, получающийся из W заменой столбца членов, содержащих (n-k)-ю степень   (i=0,1,…,n), на столбец  свободных членов системы (3.4)

. (4.7)

Подставив полученные значения коэффициентов в равенство (4.1), приходим к новой форме представления интерполяционного многочлена :

(4.8)

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

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

Согласно формуле (4.8) имеем

Разложив определитель по элементам 1-го столбца, получим

Учитывая, что

,

окончательно находим

4.3.2 Погрешность интерполяционных методов

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

Если точка интерполирования  фиксирована, то за меру погрешности естественно принять величину  - остаточный член интерполяционной формулы, зависящий от свойств функции f, параметров интерполирования и положения точки интерполяции. Если же точка  заранее не известна, а интерполирование осуществляется на отрезке , то за меру погрешности целесообразно принять величину

.

Теорема 2. Пусть

  1.  узлы  различны в месте с  принадлежат отрезку;
  2.  функция f имеет на  непрерывную производную порядка n+1.

Тогда существует такая точка , что

.

Пусть для определенности ; . Тогда равномерная на всем отрезке [a,b] оценка для фиксированной сетки.

, (4.9)

где .

4.3.3 Интерполяционный интеграл Лагранжа

Интерполяционный многочлен Лагранжа представляет собой линейную комбинацию

, (4.10)

где .

Выражение (3.10) есть многочлен степени не выше n. В узле  этот многочлен принимает значение, так как

(i=0,1,…,n);

 .

Учитывая, что

,

Можно рассмотреть его производную в точке :

и записать многочлен Лагранжа в виде

.

Величины  являются как бы весовыми многочленами соответствующих узлов и называются многочленами Лагранжа.

Интерполяционный многочлен Лагранжа для равноотстоящих узлов интерполяции (т.е.  где h – шаг интерполяции) можно записать в виде

, (4.11)

где

;                    .

Пример 2.Функция y=sin(x) задана в виде таблицы (табл.3)

Таблица 3. Данные к примеру 2

               x

                0

             

           

               y

                0

            0.707

               1

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

Прежде всего определим . Подставляя в формулу (4.11) полученное значение  и значение  при n=2, имеем

Для оценки погрешности воспользуемся формулой (4.9). Тогда  поэтому

.

При вычислении погрешности градусную меру следует перевести в радиальную.

Итак, получили .
Лекция № 11

4.3.4 Конечные разности

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

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

В математической литературе используются три типа конечных разностей: нисходящие разности  для интерполяции назад; центральные разности   для построения центральных интерполяционных формул.

Конечной разностью первого порядка называется разность между значениями функции в данном и предыдущем узлах:

……  (4.12)

Это определение можно записать в другой форме:

;  (4.13)

Конечной разностью второго порядка называется разность между значениями первой конечной разностью второго в данном и предыдущем узлах:

.  (4.14)

Аналогичным образом  определяются конечные разности произвольного порядка k:

(4.15)

В некоторых рассчитываемых ниже интерполяционных формулах  наряду с разностями (4.15) используются средние арифметические  соседних конечных разностей одного и того же порядка:

 (4.16)

Первая из этих величин используется при нечетном k, а вторая – четном k.

Рассмотрим некоторые свойства конечных разностей.

1. Нисходящие, восходящие и центральные разности связанны между собой следующими соотношениями:

 (4.17)

2. Конечная разность удовлетворяет равенству

,  (4.18)

где а и b постоянные.

3. Конечная разность связана с соответствующей производной соотношением

 (4.19)

4. Конечная разность порядка k может быть представлена в виде следующей линейной комбинации значений :

3, (4.20)

где  - число сочетаний из к элементов по j элементов (причем ).

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

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

оценивается по общим правилам вычисления погрешности.

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

.

В случае, когда все  одинаковы и равны , получаем

.

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

Так как , а  есть точное число, то искомая вычислительная погрешность имеет вид

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

4.3.5 Интерполяционные многочлены Стирлинга и Бесселя

Рассмотрим задачу построения интерполяционного многочлена для функции f, заданной своими значениями  и  равномерной сетки с шагом h.

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

Введем новую переменную t, с помощью которой начало отсчета переводится в точку :

;  (4.21)

при этом .

Используя средние арифметические соседних конечных разностей одного и того же порядка , можно получить интерполяционный многочлен Стирлинга, обычно обозначаемый :

(4.22)

Так как многочлен Стирлинга является лишь новой формой интерполяционного многочлена Лагранжа, построенного по узлам , то его остаточный член относительно переменной t можно представить в виде

;     , (4.23)

а оценку погрешности приближенного значения  (погрешности метода) – в виде

, (4.24)

где .

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

На сетке  можно получить интерполяционный многочлен Бесселя, обычно обозначаемый :

(4.25)

Так как многочлен Бесселя является еще одной представления интерполяционного многочлена Лагранжа, построенный по узлам , то его остаточный член относительно переменной t можно записать в виде:

,              (4.26)

а оценку погрешности приближенного значения  (погрешности метода) – в виде:

, (4.27)

где .

Итак, рассмотрено два интерполяционных многочлена: многочлен Стирлинга, который используется при построении многочлена четной степени и строится по нечетному числу узлов, и многочлен Бесселя, который используется при построении многочлена нечетной степени и строится по четному числу узлов.

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

, (4.28)

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

, (4.29)

т.е. когда точка интерполирования  расположена ближе к середине между узлами и . Одно из условий (4.28) или (4.29) всегда может быть обеспечено выбором соответствующего узла  в качестве .

4.3.6 Интерполяционные многочлены Ньютона

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

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

Первый интерполяционный многочлен Ньютона обычно обозначается .

. (4.30)

Остаточный член относительно переменной t можно представить в виде:

;                  , (4.31)

а оценку погрешности приближенного значения  (погрешности метода) – в виде:

, (4.32)

где .

Пусть точка  расположена вблизи последнего узла сетки . Для этой сетки, снова используя переменную t, определяемую соотношением (4.21), построим интерполяционный многочлен.

Второй интерполяционный многочлен Ньютона обычно обозначается .

. (4.33)

с остаточным членом

,               (4.34)

и оценкой погрешности приближенного значения

 , (4.35)

где .

Формулы (4.30) и (4.33) часто называют соответственно интерполяционными формулами Ньютона для интерполирования вперед и назад.


Лекция № 12

4.3.7 Разделенные разности

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

Пусть функция y = f(x) задана своими значениями ,

, ,…, , … в узлах  произвольной сетки .

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

Разделенными разностями второго порядка называются отношения

В общем случае разделенная разность k-го порядка определяется через разделенную разность(k-1)-го порядка по формуле

. (4.36)

Для разностных отношений используются и другое обозначение:

.

Приведем некоторые свойства разделенных разностей

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

. (4.37)

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

3. Разделенная разность удовлетворяет равенству

, (4.38)

4. Если узлы  принадлежат отрезку  и функция f(x) имеет на  непрерывную производную k-го порядка, то существует такая точка , что

. (4.39)

Из этого свойства вытекает простое следствие. Пусть

есть многочлен k-й степени. Тогда, очевидно, , и соотношение (4.39) дает для разделенной разности значение

Итак, у всякого многочлена k-й степени разделенные разности k – го порядка равны постоянной величине – коэффициенту при старшей степени многочлена. Разделенные разности высших порядков (больше k), очевидно, равно нулю.

4.3.8 Интерполяционный многочлен Ньютона для произвольной сетки узлов

Используя форму Лагранжа, представим интерполяционный многочлен в следующем виде:

Здесь ; ; (k = 1,2,…n) – интерполяционные многочлены в форме Лагранжа, построенные по узлам .

Рассмотрим разности

Таким образом, используя формулу (3.37), получим

 (4.40)

а интерполяционный многочлен принимает форму

 (4.41)

Эта форма называется интерполяционным многочленом Ньютона с раздельными разностями.

Выражение для погрешности имеет тот же вид, что и в случае многочлена Лагранжа [см.формулу(4.9)].

Отметим, что в формуле (4.41) интерполяционного многочлена на узлы накладывается  единственное условие - их несовпадение. Поэтому нумерацию узлов можно произвести в произвольном порядке. Например, индексом «0» часто обозначают последующий узе6л таблицы, за  принимают предпоследний узел и обозначают его  и т.д. В этом случае многочлен (4.41) принимает форму

 (4.42)

и ее называют многочленом Ньютона для интерполирования назад.

Сравнение форм Лагранжа и Ньютона интерполяционного многочлена позволяет рекомендовать использование представления в форме Лагранжа, во-первых, в теоретических исследованиях, например при изучении вопроса о сходимости   к ; во-вторых, при интерполировании нескольких функций на одной и той же сетке узлов, поскольку в этом случае можно один раз вычислить множители  Лагранжа  и использовать их для интерполяции всех функций.

Представление в форме Ньютона оказывается более удобным в практических расчетах. Действительно, число используемых узлов и степень интерполяционного многочлена  часто заранее не известно, а при переходе от n узлов к (n+1)-му узлу в форме Ньютона добавляется лишь один член, имеющий смысл поправки к уже вычисленному значению. В то же время в форме Лагранжа добавление еще одного слагаемого сопровождается и полным пересчетом полученного ранее результата. Кроме того, в вычислительной практике интерполяция обычно осуществляется на не большом отрезке длиной h<1. При этом слагаемые формы Ньютона имеет порядок   ,…, т.е. расположены в порядке убывания, что оказывается полезным при определении точности результата интерполирования.

4.3.9 Итерационно-интерполяционный метод Эйткина

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

Здесь

;

-

интерполяционный многочлен степени не выше первой, построенный по узлам ;

-

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

.

Покажем, что если и  - интерполяционные многочлены, построенные соответственно по узлам  и , то - интерполяционный многочлен, построенный соответственно по узлам .

Действительно, во-первых,  - многочлен степени не выше n, что очевидно из построения формулы (4.43). Во-вторых, во всех узлах многочлен принимает соответствующие значения:

   (;

   (;

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

4.3.10 Интерполирование  с кратными узлами

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

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

Пусть на сетке  в узлах  заданы значения некоторой функции f и ее производные

,

причем  требуется построить многочлен , значения которого и производные до порядка в узлах  (i=0,1,…,m) совпадают со значениями f и соответствующими ее производными, а также оценить погрешность.

Такой вид интерполирования называют интерполированием по Эрмиту, а  соответствующий многочлен - многочленом Эрмита. Числа называют кратностями узлов . При этом можно доказать, что многочлен Эрмита существует и единственен.

Остаточный член интерполяционной формулы …. можно представить в следующем виде:

. (4.44)

Пусть для определенности

. (4.45)

Используя это ограничение и формулу (4.44), получим оценку погрешности для фиксированной точки x:

. (4.46)

Построение равномерной на всем отрезке [a,b] оценки для фиксированной сетки  теперь не представляет труда. Действительно,

,  (4.47)

где

. (4.48)

Пример 4.4. Построить интерполяционный многочлен Эрмита  для функции  по узлам  соответственно с кратностями . Получить равномерную оценку погрешности на отрезке [-1,1].

Вычислим в заданных узлах значение функции и ее производной:

;  

Построим многочлен Эрмита с учетом кратностей узлов:

.

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

.

Нетрудно показать, что . Поэтому окончательно имеем .


Лекция № 13

4.4 Равномерное приближение функций. Приближение методом
наименьших квадратов

До сих пор рассматривалась интерполяция, т. е. такой способ приближения, когда значения приближаемой и приближающей функций совпадают в узлах некоторой сетки. Однако достаточно часто, например, при аппроксимации большого числа экспериментальных точек, найденных с некоторой погрешностью, интерполяция становится неразумной. В этом случае целесообразно строить приближающую функцию таким образом, чтобы сгладить влияние погрешности измерения и числа точек эксперимента. Такое сглаживание реализуется при построении приближающей функции по методу наименьших квадратов. Вид приближающей функции может быть произвольным, далее рассмотрен случай, когда приближающая функция является многочленом. При этом добиваются минимизации суммы квадратов отклонений значений приближаемой и приближающей функций в узлах сетки. Эта сумма называется КВАДРАТИЧНЫМ ОТКЛОНЕНИЕМ.

Пусть функция  при  задана таблично в узлах хj. Необходимо построить такой многочлен  которого минимально квадратичное отклонение

(4.49)

Очевидно, что минимума Ф можно добиться только за счет изменения коэффициента многочлена Fn(x). Необходимые условия экстремума имеют вид

,   . (4.50)

Эту систему для удобства преобразуют к виду

,    . (4.51)

Система (4.51) называется НОРМАЛЬНОЙ СИСТЕМОЙ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ и представляет собой систему линейных алгебраических уравнений относительно коэффициентов ai. Решив систему, построим многочлен Fn(x), приближающий функцию f(x) и минимизирующий квадратичное отклонение.

Рассмотрим одно важное свойство системы (4.51). Предположим, что точки равномерно распределены на отрезке [О, 1], т. е. , . В этом случае сумму  можно приближенно заменить интегралом

.

Тогда определитель  системы (4.51) составляет

,

где  — матрица Гильберта порядка  n + 1, элементы которой имеют вид . Определитель этой матрицы

весьма быстро убывает с ростом р, что приводит к быстрому убыванию величины определителя системы . Так  для р = 2 и  для р = 3. В первом случае n = 1, во втором n = 2.

Следовательно, система (4.51) с увеличением степени n приближающего многочлена становится плохо обусловленной и решение её связано с большой потерей точности. Поэтому в методе наименьших квадратов, как правило, используют приближающий многочлен не выше третьей степени. При необходимости построения многочленов большей степени применяют приемы, позволяющие повысить обусловленность системы (4.51); обычно таких приемов два. В первом используют систему точек, позволяющую разбить систему (4.51) на две подсистемы меньшего порядка, во втором — систему ортогональных многочленов,

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

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

Можно показать методами теории вероятностей, что функция , найденная по формулам (4.50), (4.51), с наибольшим правдоподобием совпадает с оценкой математического ожидания для заданной выборки , т.е. метод наименьших квадратов обладает сглаживающими свойствами.


Лекция № 14

5. Численное интегрирование и дифференцирование

5.1. Численное дифференцирование

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

Простейшие выражения для производных получаются в результате дифференцирования  интерполяционных форм.

Итак, рассмотрим следующую задачу. На сетке  в узлах  заданы значения  функции f, непрерывно дифференцируемой n+1+m раз. Требуется вычислить производную  и оценить погрешность.

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

f (x)= . (5.1)

Продифференцируем правую и левую части соотношения (5.1) m раз и положим :

. (5.2)

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

. (5.3)

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

Учитывая сказанное, а так же то, что вычисление высших производных может быть сведено к последовательному вычислению низших, остановимся более подробно на получении расчетных формул для  и  в узлах равномерной сетки. Для получения производных в узловых точках целесообразно использовать интерполяционный многочлен Стирлинга и его остаточный член. Так дифференцируя многочлен Стирлинга и его остаточный член по x и полагая  (), получим следующие выражения  для производной:

                (k=1) (5.4)

      (k=2) (5.5)

Дифференцируя многочлен Стирлинга два раза по x и вычисляя значение второй производной в точке  имеем

                    (k=1) (5.6)

      (k=2) (5.7)

Для вычисления производной точно в середине между узлами  применяют многочлен Бесселя. В этом случае соответствующие формулы для производной имеют вид

             (k=1) (5.8)

     (k=2) (5.9)

Практический интерес представляют также так называемые формулы одностороннего дифференцирования, позволяющие вычислить по узлам  (i=0,1,…,k,… или i=0,- 1,…,- k,…). Построение этих формул удобно провести с помощью первого и второго интерполяционных многочленов Ньютона.

Дифференцируя первый многочлен Ньютона по x  и вычисляя значение производной в точке  (t = 0) для k=1 и  k=2 получим соответственно следующие формулы:

(5.10)

(5.11)

Аналогично, дифференцируя второй многочлен Ньютона, для k=-1 и  k= - 2 соответственно имеем

(5.12)

(5.13)

Приведем снова все формулы второго порядка, выразив входящие в них конечные разности непосредственно через значение функции . Из соотношений (5.4), (5.6) и (5.8) имеем

(5.14)

(5.15)

(5.16)

Соотношения (4.11) и (4.13) соответственно дают

(5.17)

(5.18)

Из формул (5.17), (5.18) видно, что с уменьшением шага  сетки уменьшается и погрешность метода. Однако если значения функции   заданы приближенно, например, с одинаковой абсолютной погрешностью , то при использовании формул численного дифференцирования суммарная погрешность будет содержать дополнительное слагаемое, обратно пропорциональное  (m – порядок производной). Поэтому уменьшение h разумно лишь в определенных пределах.

Иллюстрируя сказанное, рассмотрим правую часть формулы (5.16). Суммарная погрешность ее составляет

. (5.19)

Приравнивая  нулю, получаем точку экстремума функции :

. (5.20)

Так как , то  - точка минимума , причем:

. (5.21)

Аналогично, из формулы (4.15) для оптимального шага получаем выражение

(5.22)

А из формулы (4.17) и (4.18) – выражение

(5.23)

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

Пример 5.1. Вычислить  и  для функции , заданной в виде таблицы (табл. 4.1), содержащей значение  со всеми верными в широком смысле знаками. Оценить погрешность результата.

Таблица 4. Данные к примеру 5.1

x

1,2

1,3

1,4

1,5

1,6

f

0,1823

0,2626

0,3364

0,4054

0,4700

Для вычисления требуемых производных  применим соответственно формулы (5.18) и (5.15). Тогда, используя равенства (5.21) и (5.22), а также исходные данные, получим следующие значения для оптимального шага:

при вычислении ;

при вычислении .

Так как табличные данные не позволяют выбрать в качестве шага 0,22, то за  Принимаем ближайшее возможное число 0,2. Следовательно,

,

причем суммарная погрешность не превышает

;

и

,

причем суммарная погрешность не превышает

.

В некоторых случаях для определения производной задается только таблица значений функции. Тогда оценить погрешность невозможно. Приближенные значения производной вычисляются непосредственно по одной из формул (5.17) – (5.23) без учета погрешности.

Пример 5.2. Вычислить ,  для функции f(x), заданной в виде таблицы (табл. 5).

Таблица 5. Данные к примеру 5.2

x

1,2

1,3

1,4

1,5

1,6

y=f(x)

0,18

0,26

0,34

0,41

0,47

На основании формул (5.17) и (5.19) получаем:


Лекция № 15

5.2. Формулы численного интегрирования

Пусть требуется вычислить интеграл

(5.24)

Из курса математического анализа известно, что для непрерывной на отрезке [a,b] функции f  интеграл (4.24) существует и равен разности значений для первообразной F  для функции f в точках b и a:

. (5.25)

Однако в подавляющем большинстве практических задач первообразную F не удается выразить через элементарные функции. Кроме того, функция f часто задается в виде таблицы ее значений для определенных значений аргумента. Все это порождает потребность в приближенных методах вычислении интеграла (4.24), которые можно условно подразделить на аналитические и численные. Первые заключаются в приближенном построении первообразной и дальнейшем использовании формулы (5.25). Вторые позволяют непосредственно найти числовое значение интеграла, основываясь на известных значениях подынтегральной функции (а иногда и ее производной) в заданных точках, называемых узлами. В настоящей главе остановимся лишь на численных методах интегрирования функций. Сам процесс численного определения интеграла называется квадратурой, а соответствующие формулы – квадратурными.

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

Задача 1. На отрезке [a,b]  в узлах  заданы значения  некоторой функции f, принадлежащей определенному классу F. Тре6уется приближенно вычислить интеграл (5.24) и оценить погрешность полученного значения. Так обычно ставится задача численного интегрирования в том случае, когда подынтегральная функция задана в виде таблицы.

Задача 2. На отрезке [a,b] функция f(x) задана в виде аналитического выражения. Требуется вычислить интеграл (5.24) с заданной предельно допустимой погрешностью.

Один из способов решения сформулированных задач основан на использовании различных квадратурных формул вида

(5.26)

С известным остаточным членом  или его оценкой.

В общем случае, как узловые точки , так и весовые множители (веса)  заранее не известны  и подлежат определению при выводе каждой конкретной квадратурной формулы на основе предъявляемых к ней требований.

По существу, задача численного интегрирования эквивалентна оценке среднего значения функции. Действительно, среднее значение функции на отрезке [a,b]  определяется следующем образам:

.

Поэтому

.

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

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

Алгоритм решения задачи 1.

1о. Выбирают конкретную квадратурную формулу (5.26) и вычисляют . Если значения функции  заданы приближенно, то фактически вычисляют лишь приближенное значение  для точного .

2о. Приближенно принимают, что

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

.

4о. Определяют погрешность вычисления :

по погрешности приближения значений .

5о. Находят полную абсолютную погрешность приближенного значения :

.

6о. Получают решение задачи в виде

.

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

Алгоритм решения задачи 2.

1о. Представляют  в виде суммы трех неотрицательных слагаемых:

,

где  - предельно допустимая погрешность метода;  - предельно допустимая погрешность вычисления ;  - предельно допустимая погрешность округления результата.

2о. Выбирают n в квадратурной формуле так, чтобы выполнялось неравенство

.

3о. Вычисляют  с такой точностью, чтобы при подсчете  по формуле (5.26) обеспечить выполнение неравенства

.

Для этого, очевидно, достаточно вычислить все  с абсолютной погрешностью.

.

4о. Найденную в п. 3о величину  округляют (если ) с предельно допустимой погрешностью  до величины .

5о. Получают решение задачи в виде

.

Используемые в алгоритмах обеих задач квадратурные формулы строятся, как уже было сказано, на основании тех или иных критериев, определяющих положение узловых точек и величины весовых множителей. Такими критериями могут быть: представление интеграла в виде интегральной суммы; аппроксимация подынтегральной функции (например, многочленом) и последующее интегрирование аппроксимирующей функции; требование, чтобы формула (4.26) была абсолютно точной для определенного класса функций, и др.

Простейшие квадратурные формулы

Формулы прямоугольников. Как известно, определенный интеграл в силу своего построения есть предел интегральных сумм:

, (5.27)

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

Ограничиваясь конечным числом слагаемых в правой части равенства (5.27) и принимая в качестве набора  те или иные значения аргумента из отрезков , можно получить различные формы приближенного интегрирования. Так, принимая в качестве набора  значения левых или правых концов отрезков , получим соответственно формулу левых или правых прямоугольников :

, (5.28)

. (5.29)

Название этих формул связано с их геометрической интерпретацией. Если в плоскости Х0У (рис 11) построить кривую y = f(x), разбить отрезок  на n частей точками  сетки , то формула левых прямоугольников в качестве приближенного значения интеграла даст суммарную площадь штрихованы прямоугольников (рис. 11, а); а формула правых прямоугольников - суммарную площадь штрихованы прямоугольников (рис. 11, б).

Рисунок 11 – Графическая интерпретация формулы прямоугольников

Пример 5.3. с помощью формул левых и правых прямоугольников вычислить , полагая n = 4.

Зная приделы интегрирования  a = 1 и b = 9, находим шаг ; тогда точками разбиения служат , , , , , а значения подынтегральной функции  в этих точках таковы:

Далее найдем числовое значение интеграла, пользуясь  формулой (4.28):

Если вычисление определенного интеграла произвести по формуле (4.29), то получим:

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

,  (5.30)

где ; ; .

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

. (5.31)

Предполагая, что функция f(x) дважды дифференцируема, т.е. , запишем для функции f(x) на каждом из отрезков  формулу Тейлора  остаточным членом в форме Лагранжа:

   (5.32)

Подставим в правую часть соотношения (5.31) вместо функции f ее представление (4.32) и выполним интегрирование, используя вторую теорему о среднем значении функции:

  

В силу непрерывности второй производной существует такая точка , что

Используя это соотношение, окончательно имеем

 (5.33)

Сравнивая формулы (4.30) и (4.33), получаем выражение для остаточного члена квадратурной формулы (4.30):

 (5.34)

Таким образом, оценку погрешности квадратурной формулы (5.30) можно представить в следующем виде:

 (5.35)

где

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

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

 (5.36)

Эта погрешность не зависит от числа разбиений отрезка интегрирования, а пропорциональна только его длине.

Пример 5.4. Вычислить с помощью формулы прямоугольников интеграл , полагая n = 4. Оценить погрешность полученного приближенного значения.

По заданным пределам интегрирования и числу разбиений n определим шаг:

. далее на основании формулы (5.30) имеем

Вычислив необходимые значения функции с тремя верными в узком смысле знаками , получим

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

Таким образом, погрешность метода есть

Пользуясь формулой (5.36), найдем вычислительную погрешность:

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

Формула трапеций. Перейдем теперь к другому способу построения квадратурных формул, связанному с аппроксимацией подынтегральной функции интерполяционным многочленом. Рассмотрим простейший случай аппроксимации многочленом первой степени с узлами в точках a и b:

;       .

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

;      .

Таким образом, предполагая, что отрезок интегрирования мал, получаем квадратурную формулу, называемую формулой трапеций:

(5.37)

с остаточным членом

;     . (5.38)

Используя выражение (4.35) для остаточного члена, опенку погрешности квадратурной формулы (4.37) можно представить в виде

, (5.39)

где .

Полученные выражения для остаточного члена (5.38) и погрешности (5.39) показывают, что квадратурная формула (5.37) является точной для всех линейных функций, поскольку вторая производная таких функций равна нулю, а, следовательно, равны пулю остаточный член и погрешность.

Пример 5.5.  Вычислить с помощью формулы трапеций интеграл .    Оценить погрешность полученною приближенного значения.

На основании формулы (5.37) имеем

.

Вычислив необходимые значения функции, получим

.

Погрешность метода оценим по формуле (5.39), используя значение М=2 полученное в примере 5.4:

.

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

Итак, окончательно имеем .

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

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

Квадратурные формулы Ньютона – Котеса.

Рассмотрим формулы численного интегрирования, имеющие более сложную структуру. Описанные выше методы численного интегрирования являлись интерполяционными, включая в определенном смысле и формулы прямоугольников. Это означает, что подынтегральная функция аппроксимировалась интерполяционным многочленом. Если ни интегрируемая функция достаточно гладкая, а отрезок интегрирования конечен, то можно получить достаточно хорошие результаты. С другой стороны, трудно рассчитывать на хорошую аппроксимацию интегрируемой функции многочленом, если сама функция или ее производные невысоких порядков имеют особенности. В таких случаях подынтегральную функцию целесообразно представить в виде произведения двух сомножителей:, которые должны обладать следующими тремя свойствами. Во-первых, весовой множитель р(х) должен отражать все особенности интегрируемой функции. Во-вторых, моменты

      (k = 0,1,…),

где [а, b] - отрезок интегрирования, должны вычисляться аналитически.

В-третьих, погрешность аппроксимации функции f(x)  многочленом должна быть мала.

Перейдем теперь к построению самих квадратурных формул. Будем их строить в том же виде, что и раньше:

. (5.41)

В общем случае, как уже отмечалось, формула (5.41) имеет 2n свободных параметров - это узлы квадратуры  и весовые множители. Число n будем предполагать фиксированным. Выбор свободных параметров определяется теми требованиями, которые предъявляются к квадратурной формуле условиями практической задачи. Такими требованиями могут быть, например, максимально возможная точность, минимальная вычислительная погрешность, фиксирование некоторых (а возможно, и всех) весовых множителей или узлов квадратуры.

Начнем с относительно простого случая, когда узлы определены заранее и можно варьировать лишь выбором весовых множителей. Идея интерполяционных квадратур заключается в следующем. Аппроксимируем функцию f интерполяционным многочленом в форме Лагранжа степени n-1 по n различным узлам:

.

Проинтегрируем правую и левую части этого равенства на отрезке [а,b], предварительно умножив их на весовую функцию р(х):

.  (5.42)

Преобразуем первое слагаемое правой части этого соотношения.

Для этого подставим вместо  его явное выражение и поменяем местами операции интегрирования и суммирования:

. (5.43)

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

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

            (i = 1,2,…,n). (5.44)

Построенная таким образом квадратурная формула называется интерполяционной.

Перейдем к оценке погрешности формулы (5.41) с коэффициентами (5.44). Для лото проинтегрируем остаточный член интерполяционной формулы:

.

Подставляя приведенное выражение во второе слагаемое равенства (5.42), получаем

;     .

Если функция f имеет на отрезке итерирования непрерывную производную порядка и, а произведение сохраняет на том же отрезке свой знак, то дли остаточного члена можно получить следующее выражение:

;      . (5.45)

и, следовательно, оценка погрешности квадратуры принимает вид

, (5.46)

где Полученная оценка при указанных выше условиях является не улучшаемой.

Если же произведение  не сохраняет знак па отрезке интегрирования, но в этом случае получается лишь грубая оценка погрешности:

,

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

Пример 5.6. Построить квадратурную формулу (4.41) дли отрезка [-1,1] с узлами  и весовой функцией.

По существу, необходимо определить коэффициенты A, (i = 1,2,3) формулы (5.41). Используя выражение (5.44) для искомых коэффициентов, получаем

,

,

.

Таким образом, искомая формула имеет вид

.

В практических расчетах особый интерес представляет случай, когда узлы квадратурной формулы задаются в виде равноотстоящих точек отрезка [а, b]:  (i = 1,2,…,n), а весовая функция р(х) тождественно равна единице. При таких предположениях формулу (5.41) можно преобразовать к виду

. (5.47)

При различных n получаем квадратурные формулы Ньютона-Котеса. Коэффициенты, называемые коэффициентами Котеса, определяются из соотношения (4.44):

, (5.48)

где n >1; i = 1,2,…,n; 0!=1.

Эти коэффициенты обладают следующими полезными при их вычислении свойствами.

1. Симметричные коэффициенты (первый и n-й, второй и (n-1)-й, ...) равны между собой:

. (5.49)

2. Сумма всех коэффициентов равна единице:

.

В табл. 6 приведены значения коэффициентов Котеса для
n = 2,3,4,5,6.

Таблица 6. Значения коэффициентов Котеса для n = 2,3,4,5,6

n

i = 1

i = 2

i = 3

i = 4

i = 5

i = 6

2

1/2

1/2

-

-

-

-

3

1/6

4/6

1/6

-

-

-

4

1/8

3/8

3/8

1/8

-

-

5

7/90

32/90

12/90

32/90

7/90

-

6

19/288

75/288

50/288

50/288

75/288

19/288

Остановимся па частном случае квадратурной формулы (5.47), получающемся при n = 3. Применяя формулу (5.48), имеем

.

Далее, используя равенства (4.49), найдем

,    .

Таким образом, искомая квадратурная формула, называемая формулой Симпсона, имеет вид

.  (5.50)

Формула (5.50) является точной для всех многочленов нулевой, первой, и второй степеней. Формула Симпсона обладает также так называемым свойством повышенной точности, которое заключается в том, что она является точной не только для многочленов второй степени, но и для многочленов третьей степени.

Оценка погрешности имеет вид

, (5.51)

где .

Пример 5.7. Вычислить с помощью формулы Симпсона интеграл . Оценить погрешность полученного приближения.

Вычислив необходимые значения подынтегральной функции в точках , подставим их в формулу (5.50):

.

Учитывая, что , и используя формулу (5.51), для метода получим погрешность .

Найдем вычислительную погрешность

.

Складывая погрешности и округляя результат, окончательно имеем

.


Лекции № 16

5.3. Решение обыкновенных дифференциальных уравнений. Метод конечных разностей для численного решения дифференциальных уравнений

Метод последовательных приближений (метод  Пикара)

Пусть дано уравнение

, (5.52)

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

    . (5.53)

Интегрируя обе части уравнения от до получим

или

. (5.54)

Уравнение (5.52) заменяется интегральным уравнением (5.3), в котором неизвестная функция у находится под знаком интеграла. Интегральное уравнение (5.54) удовлетворяет дифференциальному уравнению (5.52) и начальному условию (5.53). Действительно,

Заменяя в равенстве (5.54) функцию у значением , получим первое приближение

.

Затем в уравнении (5.54) заменив у найденным значением , получаем второе приближение:

.

Продолжая процесс далее, последовательно находим

,

.

Таким образом, составляем последовательность функций

.

Справедлива следующая теорема.

Теорема 6.1. Пусть в окрестности точки  функция f(х,у) непрерывна и имеет ограниченную частную производную . Тогда в некотором интервале, содержащем точку , последовательность  сходится к функции у(х), служащей решением дифференциального уравнения у = f(x,y) и удовлетворяющей условию

у(х0) = у0.

Оценка погрешности метода Пикара определяется, но формуле

,

где  при ;  - постоянная Липшица для области ;  - величина определения окрестности ; a и b – границы области R.

Интегрирование дифференциальных уравнений
с помощью степенных рядов

Метод последовательного дифференцирования. Пусть дано дифференциальное уравнение  n-го порядка:

(5.55)

с начальными условиями

. (5.56)

Правая часть этого уравнения есть аналитическая функция в начальной точке . Представим решение  уравнения (5.55) в окрестностях точки х0 в виде ряда Тейлора:

(5.57)

где , а h – достаточно малая величина.

Для нахождения коэффициентов ряда (5.57) уравнение (5.55) дифференцируют по х нужное число раз, используя условия (5.56).

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

Если, то получается ряд Тейлора по степеням х:

(5.58)

Метод неопределенных коэффициентов. Пусть дано дифференциальное уравнение

, (5.59)

с начальным условием .

Метод неопределенных коэффициентов состоит в том, что решение уравнения (5.59) отыскивают в виде ряда с неизвестными коэффициентами

(5.60)

которые находят с помощью подстановки ряда (5.60) в уравнение (5.59), зачем приравнивают коэффициенты при одинаковых степенях х и используют начальное условие. Найденные значения коэффициентов  подставляют в ряд (5.60).

Метод Эйлера

Решить дифференциальное уравнение  численным методом - это значит для заданной последовательности аргументов  и числа , не определяя функцию у = F(x), найти такие значения  что  (i = 1,2,...,n) и .

Таким образом, численные методы позволяют вместо нахождения функции у = F(x) получить таблицу значений этой функции для заданной последовательности аргументов. Величина  называется шагом интегрирования. Рассмотрим некоторые из численных методов.

Метод Эйлера является сравнительно грубым и применяется в основном для ориентировочных расчетов.

Пусть дано дифференциальное уравнение первого порядка

,  (5.61)

с начальным условием

. (5.62)

Требуется найти решение уравнения (5.61) на отрезке [а, b].

Разобьем отрезок [а,b] на n равных частей и получим последовательность , где  (i = 1, 2,..., n), a  - шаг интегрирования.

Выберем k-й участок  и проинтегрируем уравнение (5.61):

. (5.63)

Тогда формула (5.63) примет вид

 (5.64)

Обозначив,  т.е. , получим

(5.65)

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

Если функция f(x,y) в некотором прямоугольнике

удовлетворяет условию

            (N = const)  (5.66)

и, кроме того.

             (М = const) (5.67)

 то имеет место следующая оценка погрешности:

, (5.68)

где  - значение точного решения уравнения (5.61) при ,а  - приближенное значение, полученное на n-м шаге.

Формула (5.68) имеет в основном теоретическое применение. На практике, как правило, применяют "двойной просчет". Сначала расчет ведется с шагом h, затем шаг дробят и повторный расчет ведется с шагом . Погрешность более точного значения  оценивается формулой

(5.69)

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

Пусть задана система двух уравнений первого порядка

(5.70)

с начальными условиями

,      (5.71)

Приближенные значения  и  находятся по формулам

,      (5.72)

где ,    (i = 0,1,2,…).  (5.73)

Метод Рунге-Кутта

Метод Рунге-Кутта является одним из методов повышенной точности. Он имеет много общего с методом Эйлера.

Пусть на отрезке [а, b] требуется найти численное решение уравнения

,  (5.74)

с начальным условием

. (5.75)

Разобьем отрезок [а, b]  на n равных частей точками  
(
i = 1,2,..., n, a  - шаг интегрирования). В методе Рунге-Кутта, так же, как и в методе Эйлера, последовательные значения у, искомой функции у определяются по формуле

. (5.76)

Если разложить функцию у в ряд Тейлора и ограничиться членами до  включительно, то приращение функции  можно представить в виде

, (5.77)

где производные , ,  находят последовательным дифференцированием из уравнения (5.74).

Вместо непосредственных вычислений по формуле (5.26) методом Рунге-Кутта определяют четыре числа:

(5.78)

Можно доказать, что если числам    придать соответственно веса 1/6; 1 / 3; 1 / 3; 1 / 6, то средневзвешенное этих чисел, т.е.

(5.79)

с точностью до четвертых степеней равно значению , вычисленному по формуле (5.77):

. (5.80)

Таким образом, для каждой пары текущих значений  и  по формулам (5.27) определяют значения

(5.81)

Метод Рунге-Кутта имеет порядок точности  на всем отрезке [а,b]. Оценка точности этого метода очень затруднительна. Грубую оценку погрешности можно получить с помощью "двойного просчета" по формуле

, (5.82)

где  - значение точного решения уравнения (5.74) в точке  а  и  - приближенные значения, полученные с шагом h/2 и h.

Если  - заданная точность решения, то число n (число делений) для определения шага интегрирования  выбирается таким образом, чтобы

. (5.83)

Однако шаг расчета можно менять при переходе от одной точки к другой.

Для оценки правильности выбора шага h используют равенство

, (5.84)

где q должно быть равно нескольким сотым, в противном случае шаг h уменьшают.

Метод Рунге-Кутта может быть применен и к решению систем дифференциальных уравнений.

Пусть задана система дифференциальных уравнений первого порядка

(5.85)

с начальными условиями

,   ,   . (5.86)

В этом случае параллельно определяются числа  и :

(5.87)

где  ;

;

;

;

;

;

;

.

Тогда получим решение системы

,     . (5.88)

Экстраполяционный метод Адамса

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

Пусть дано дифференциальное уравнение

,  (5.89)

с начальным условием

,     . (5.90)

Требуемся найти решение этого уравнения на отрезке [a.b].

Разобьем отрезок [a,b] на n равных частей точками  
(
i = 1, 2,..., n), a  – проинтегрируем дифференциальное уравнение). Выберем участок   и проинтегрируем дифференциальное уравнение (5.89); тогда получим

,

или

. (5.91)

Для нахождения производной воспользуемся второй интерполяционной формулой Ньютона (ограничиваясь при этом разностями третьего порядка):

. (5.92)

или

. (5.93)

Подставляя выражение для  из формулы (5.93) в соотношение (5.91) и учитывая, что , имеем

(5.94)

Обозначим в дальнейшем    (i = 0,1,2,…,n).

Тогда для любой разности имеем  и

. (5.95)

По формуле  получаем решение уравнения. Формула (5.95) носит название экстраполяционной формулы Адамса.

Для начала процесса нужны четыре начальных значения  - так называемый начальный отрезок, который может быть найден, исходя из начального условия (5.90) с использованием одного из известных методов. Обычно начальный отрезок решения находится методом Рунге-Кутта.

Зная  можно определить

;     ;

;     . (5.96)

Далее составляется таблица разностей величины q (табл. 7).

Таблица 7. Таблица разностей величины q

I

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

0

-

1

-

-

2

-

-

-

3

-

-

-

4

-

-

-

-

-

-

5

-

-

-

-

-

-

-

6

-

-

-

-

-

-

-

Метод Адамса заключается в продолжении диагональной таблицы разностей с помощью формулы (5.95). Используя числа , которые располагаются в таблице по диагонали, пологая в формуле (5.95)
n = 3 (известное последнее значение у есть ), получаем:

.

Полученное значение  вносят и таблицу и находят . Затем используя значения  и  находят  т.е. получается новая диагональ. По этим данным вычисляют

    .

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

Для грубой оценки погрешности применяют принцип Рунге, который состоит в следующем:

  1.  Находят решение дифференциального уравнения при шаге h.
  2.  Значение шага удваивают и находят решение при шаге Н = 2h.

3.  Вычисляют погрешность метода по формуле

, (5.97)

где  - значение приближенного вычисления при двойном шаге H=2h;  - значение приближенного вычисления при шаге h.

Метод Адамса применяется также и для решения систем дифференциальных уравнений и дифференциальных уравнений no порядка.

Пусть  задана система двух уравнений

(5.98)

Тогда экстраполяционные формулы Адамса для этой системы  имеют вид

(5.99)

где    и ,

.


Лекции № 17

5.4. Преобразование Фурье

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

Существует множество тесно связанных разновидностей этого преобразования.

5.4.1 Применения преобразования Фурье

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

  •  Преобразования являются линейными операторами и, с соответствующей нормализацией, также являются унитарными (свойство, известное как теорема Парсеваля или, в более общем случае как теорема Планшереля, или в наиболее общем как дуализм Понтрягина).
  •  Преобразования обратимы, причем обратное преобразование имеет практически такую же форму, как и прямое преобразование.
  •  Синусоидальные базисные функции являются собственными функциями дифференцирования, что означает, что данное представление превращает линейные дифференциальные уравнения с постоянными коэффициентами в обычные алгебраические. (Например, в линейной стационарной системе частота — консервативная величина, поэтому поведение на каждой частоте может решаться независимо.)
  •  По теореме о свёртке, преобразование Фурье превращает сложную операцию свертки в простое умножение, что означает, что они обеспечивают эффективный способ вычисления основанных на свёртке операций, таких как умножение многочленов и умножение больших чисел.
  •  Дискретная версия преобразования Фурье может быстро рассчитываться на компьютерах, используя алгоритм быстрого преобразования Фурье (БПФ, англ. FFT).

5.4.2 Разновидности преобразования Фурье

Непрерывное преобразование Фурье

Наиболее часто термин «преобразование Фурье» используют для обозначения непрерывного преобразования Фурье, представляющего любую квадратично-интегрируемую функцию f(t) как сумму (интеграл Фурье) комплексных показательных функций с угловыми частотами ω и комплексными амплитудами . Преобразование имеет несколько форм, отличающихся постоянными коэффициентами.

,

,

,

где ω = 2πν.

В разных областях науки и техники могут преобладать различные формы (поэтому иногда надо уточнять определение). Обобщенным случаем такого преобразования является дробное преобразование Фурье, посредством которого преобразование можно возвести в любую вещественную «степень».

Ряды Фурье

Непрерывное преобразование само фактически является обобщением более ранней идеи рядов Фурье, которые определены для периодических функций или функций, существующих на ограниченной области f(x) (с периодом ), и представляют эти функции как ряды синусоид:

,

где Fn — комплексная амплитуда. Или, для вещественнo-значных функций, ряд Фурье часто записывается как:

,

где an и bn — (действительные) амплитуды ряда Фурье.

Дискретное преобразование Фурье

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

,

где fj — амплитуды Фурье. Хотя непосредственное применение этой формулы требует  операций, этот расчет может быть сделан за  операций используя алгоритм быстрого преобразования Фурье (БПФ, FFT) (см. O-большое), что делает преобразование Фурье практически важной операцией на компьютере.

Оконное преобразование Фурье

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

где даёт (вообще говоря несколько искажённое) распределение частот части оригинального сигнала f(t) в окрестности времени t.

Другие варианты

Дискретное преобразование Фурье является частным случаем (и иногда применяется для аппроксимации) дискретного во времени преобразования Фурье (DTFT), в котором xk определены на дискретных, но бесконечных областях, и таким образом спектр является непрерывным и периодическим. Дискретное во времени преобразование Фурье является по существу обратным для рядов Фурье.

Эти разновидности преобразования Фурье могут быть обобщены на преобразования Фурье произвольных локально сжатых абелевых топологических групп, которые изучаются в гармоническом анализе; они преобразуют группу в ее дуальную группу. Эта трактовка также позволяет сформулировать теорему свёртки, которая устанавливает связь между преобразованиями Фурье и свёртками. См. также дуализм Понтрягина для обобщенных обоснований преобразования Фурье.

5.4.3 Интерпретация в терминах времени и частоты

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

Когда функция f является функцией времени и представляет физический сигнал, преобразование имеет стандартную интерпретацию как спектр сигнала. Абсолютная величина получающейся в результате комплексной функции F представляет амплитуды соответствующих частот (ω), в то время как фазовые сдвиги получаются как аргумент этой комплексной функции.

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

5.4.4 Таблица важных преобразований Фурье

Следующая таблица содержит список важных формул для преобразования Фурье F(ω) и G(ω) обозначают фурье компоненты функций f(t) и g(t), соответственно. f и g должны быть интегрируемыми функциями или обобщенными функциями.

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

Таблица 8. Таблица преобразований Фурье

 

Функция

Образ

Примечания

1

Линейность

2

Запаздывание

3

Частотный сдвиг

4

Если  большое, то  сосредоточена около 0 и становится плоским

5

Свойство преобразования Фурье от n-ой производной

6

Это обращение правила 5

7

Запись означает свёртку и . Это правило — теорема о свёртке

8

Это обращение 7

9

означает дельта-функцию Дирака

10

Обращение 9.

11

Здесь, — натуральное число, — n-ая обобщённая производная дельта-функции Дирака. Следствие правил 6 и 10. Использование его вместе с правилом 1 позволяет делать преобразования любых многочленов

12

Следствие 3 и 10

13

Следствие 1 и 12 с использованием формулы Эйлера 

14

Также из 1 и 12

15

Показывает, что функция Гаусса  совпадает со своим изображением

16

Прямоугольная функция — идеальный фильтр низких частот и sinc функция её временной эквивалент

17

Здесь  — sign функция. Это правило согласуется с 6 и 10

18

Обобщение 17

19

Обращение 17

20

Здесь  — функция Хевисайда. Следует из правил 1 и 19


 

А также другие работы, которые могут Вас заинтересовать

42520. Определение коэффициента взаимоиндукции двух катушек 67.5 KB
  Оборудование: мост переменного тока магазин индуктивности источник переменного тока. Краткие теоретические сведения Если в проводнике изменяется сила тока то в нём возникает ЭДС самоиндукции 22. Если подключить такую катушку в цепь переменного тока то вследствие периодического изменения силы тока возникает ЭДС самоиндукции препятствующая приложенному напряжению.
42521. Снятие кривой намагничения и петли гистерезиса с помощью осциллографа 142.5 KB
  Краткие теоретические сведения Ферромагнетикам свойственно явление гистерезиса. Замкнутая кривая bcdef называется петлёй гистерезиса рис. Можно получить семейство петель гистерезиса по способу описанному ранее не доводя намагничение образца до насыщения.
42522. Определение ёмкости конденсаторов 104 KB
  Оборудование: регулятор напряжения ЛАТР миллиамперметр переменного тока на 250 мА вольтметр на 150 В конденсаторы. Если конденсатор включить в цепь постоянного тока то спустя некоторое время он зарядится т. Если конденсатор включить в цепь переменного тока то он будет перезаряжаться с частотой переменного ток и в подводящих проводах всё время будут перемещаться электрические заряды т.
42523. Изучение процессов зарядки и разрядки конденсаторов 240.5 KB
  Цель работы: изучить процессы, происходящие в цепи при зарядке (разрядке) конденсаторов, освоить метод расчёта ёмкости конденсаторов по данным о временной зависимости тока зарядки (разрядки). Оборудование: конденсатор, набор резисторов, микроамперметр на 100 мкА, источник питания постоянного тока, выключатель, секундомер, соединительные провода.
42524. Определение горизонтальной составляющей индукции земного магнетизма с помощью тангенс-гальванометра 102 KB
  Южный полюс магнитного поля Земли находится вблизи северных берегов Америки около 750 северной широты и 1010 западной долготы а северный полюс − в Антарктиде около 670 южной широты и 1400 восточной долготы. Существование магнитного поля Земли непосредственно подтверждается отклонением лёгкой магнитной стрелки при её свободном подвесе. При этом последняя устанавливается в направлении касательной к линии индукции магнитного поля Земли.
42525. Изучение однофазного трансформатора 118 KB
  Принцип действия трансформатора основан на использовании явления электромагнитной индукции. Знак − указывает на то что ЭДС в первичной и вторичной обмотках трансформатора противоположены по фазе. Создаваемый этим током магнитный поток Ф0 концентрируется в магнитопроводе и пронизывает все обмотки трансформатора индуцируя в первичной обмотке ЭДС самоиндукции 27.
42526. Определение длины электромагнитной волны в двухпроводной линии 96 KB
  Исследование электромагнитных волн в пространстве связано с некоторыми экспериментальными трудностями поэтому Лехером была предложена система состоящая из двухпроводной линии источника и приёмника электромагнитных волн. В двухпроводной линии реализуются два различных процесса передачи электромагнитного поля: с помощью токов проводимости и с помощью токов смещения. В этом случае электрические явления существенно зависят от сопротивления линии и следовательно от материала проводников.
42527. Определение ЭДС источника тока с помощью двух вольтметров 76.5 KB
  Оборудование: источник ЭДС постоянного тока два вольтметра. Физическая величина равная работе Астор сторонних сил по перемещению единичного положительного заряда вдоль всей замкнутой электрической цепи называется электродвижущей силой ЭДС 29.6 рассчитать ЭДС источника.
42528. ИЗУЧЕНИЕ РАБОТЫ ЭЛЕКТРОННОГО ОСЦИЛЛОГРАФА 353.5 KB
  Эти процессы графически изображаются на экране электронно-лучевой трубки ЭЛТ которая является основным органом электронного осциллографа. Наблюдение изображения на экране осциллографа называется осциллографированием. Изображение на экране или его фотография называется осциллограммой. Подводя отрицательный потенциал к цилиндру можно уменьшить количество электронов проходящих через его отверстие а следовательно уменьшить и яркость пятна на экране трубки.