Особенности машинной арифметики, точность вычислений на эвм

ВВЕДЕНИЕ

Цикл лабораторных работ предназначен для студентов второго курса (четвертый семестр), изучающих дисциплину "Вычислительная математика" и работающих в компьютерных классах на базе ЭВМ типа IBM PC AT-286 и выше, снабженных компилятором языка С (С++). Первые две работы цикла посвящены особенностям машинной арифметики, точности вычислений на ЭВМ и обусловленности вычислительной задачи. Они служат практической иллюстрацией вводной части теоретического курса дисциплины. Каждая из последующих работ ставит целью изучение либо конкретного численного метода, либо набора численных процедур (схем, формул), позволяющих реализовать выполнение одной из классических задач вычислительной математики: решение нелинейных уравнений, интерполирование функций, численное интегрирование, решение систем линейных алгебраических уравнений. Порядок расположения лабораторных работ в методических указаниях соответствует последовательности изложения лекционного материала. Для углубленного изучения перечисленных выше задач и методов их решения целесообразно воспользоваться литературой [1-10], приведенной в библиографическом списке.

Выполнение каждой лабораторной работы следует осуществлять поэтапно в следующем порядке:

- подготовка к решению задачи на персональной ЭВМ (ПЭВМ);

- проведение вычислительного эксперимента на ПЭВМ;

- анализ результатов вычислений; оформление отчета.

Подготовка к решению задачи на ПЭВМ производится как вне компьютерного класса, так и непосредственно на ПЭВМ. Она включает:

- ознакомление с описанием работы и заданием для выполнения;

- составление программных модулей, содержащих определенные заданием и персональным вариантом вычислительной процедуры, и/или ввод исходных данных;

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

- планирование вычислительного эксперимента на ПЭВМ в рамках выполняемого задания.

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

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

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

Анализ результатов и оформление отчета производится вне компьютерного класса.

Отчет должен содержать:

- постановку задачи;

- тексты разработанных программ;

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

- развернутые выводы по лабораторной работе.

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

 

Общие сведения

 

Пусть задана непрерывная функция вещественного аргумента x и требуется численным методом решить уравнение , т.е. найти приближение x^* к вещественному корню этого уравнения. Если уравнение имеет несколько вещественных корней, то сначала производят их отделение (изоляцию), а затем уточняют положение отдельного корня. Считается, что отделение корня произведено, если выделен такой интервал [a₀, b₀] области определения функции , на концах которого значения функции (a₀) и (b₀) имеют разные знаки и внутри которого имеется ровно один корень уравнения . Для уточнения метода используют итерационные методы, такие как метод бисекции (половинного деления), метод хорд (секущих или ложного положения), метод Ньютона (касательных), метод итераций (последовательных приближений). В указанных методах вычисляются либо последовательность значений границ сужающихся интервалов a₀, b₀, a₁, b₁,..., a_n, b_n,..., содержащих корень, либо последовательность приближений к корню x₀, x₁, x₂,..., x_n,...[2,7,8,11].

В первом случае итерационный процесс заканчивается, как только длина текущего интервала становится достаточно малой (например, ½b_n-a_n½<e). Во втором случае условием остановки вычислений является малость очередного приращения h_n=x_n-x_n-1, ½h_n½<e. В обоих случаях параметр e определяет момент остановки вычислений. Иногда в качестве условия остановки используют условие ½ () ½<e, где - текущее приближение к корню, например, =1/2(a_n + b_n ) в методе бисекции. Выполнение этого условия свидетельствует о малости значения функции в точке , т.е. позволяет считать, что ()»0.

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

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

 

Метод бисекции

(Лабораторная работа №3)

 

Если найден отрезок [a,b], такой, что (a) (b)<0, существует точка c, в которой значение функции равно нулю, т.е. (с)=0, сÎ(a,b). Метод бисекции состоит в построении последовательности вложенных друг в друга отрезков, на концах которых функция имеет разные знаки. Каждый последующий отрезок получается делением пополам предыдущего. Процесс построения последовательности отрезков позволяет найти нуль функции (корень уравнения с любой заданной точностью.

Рассмотрим один шаг итерационного процесса. Пусть на (n-1)-м шаге найден отрезок [a_n-1, b_n-1]Ì[a, b], такой, что (a_n-1) (b_n-1)<0. Разделим его пополам точкой x=(a_n-1 +b_n-1)/2 и вычислим (x). Если (x)=0, то x=(a_n-1+b_n-1)/2- корень уравнения. Если (x)¹0, то из двух половин отрезка выбирается та, на концах которой функция имеет противоположные знаки, поскольку искомый корень лежит на этой половине, т.е.

a_n=a_n-1, b_n=x, если (x) (a_n-1) < 0;

a_n=x, b_n= b_n-1, если (x) (a_n-1) > 0.

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

Метод бисекции является простым и надежным методом поиска простого корня уравнения (простым называется корень x=c дифференцируемой функции , если (с) и (с)¹0). Этот метод сходится для любых непрерывных функций , в том числе недифференцируемых. Скорость его сходимости невысока. Для достижения точности e необходимо совершить N»log₂(b-a)/e итераций. Это означает, что для получения каждых трех верных десятичных знаков необходимо совершить около 10 итераций.

В лабораторной работе №3 предлагается, используя программы - функции BISECT и Round из файла methods.cpp (файл заголовков metods.h, директория LIBR1), найти корень уравнения методом бисекции с заданной точностью Eps, исследовать зависимость числа итераций от точности Eps при изменении Eps от 0.1 до 0.000001, исследовать обусловленность метода (чувствительность к ошибкам в исходных данных).

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

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

1) Графически или аналитически отделить корень уравнения (т.е. найти отрезки [Left, Right], на которых функция удовлетворяет условиям теоремы Коши).

2) Составить подпрограмму вычисления функции .

3) Составить головную программу, содержащую обращение к подпрограмме f(x), BISECT, Round и индикацию результатов.

4) Провести вычисления по программе. Построить график зависимости числа итераций от Eps.

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

Текст программы-функции BISECT, предназначенной для решения уравнения методом бисекции, представлен в подразделе 3.7.

 

Метод хорд

(Лабораторная работа №4)

 

Пусть найден отрезок [a, b], на котором функция меняет знак. Для определенности положим (a)>0, (b)<0. В методе хорд процесс итераций состоит в том, что в качестве приближений к корню уравнения принимаются значения c₀, c₁,... точек пересечения хорды с осью абсцисс, как это показано на рис.1.

 

Сначала находится уравнение хорды АВ:

Для точки пересечения ее с осью абсцисс (x=c₀, y=0) получается уравнение

Далее сравниваются знаки величин (a) и (с₀) и для рассматриваемого случая оказывается, что корень находится в интервале (a, c₀), так как (a) (с₀)<0. Отрезок [c₀,b] отбрасывается. Следующая итерации состоит в определении нового приближения c₁ как точки пересечения хорды АВ₁ с осью абсцисс и т.д. Итерационный процесс продолжается до тех пор, пока значение (c_n) не станет по модулю меньше заданного числа e (см. подраздел 3.1).

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

В лабораторной работе №4 предлагается, используя программы - функции HORDA и Round из файла methods.cpp (файл заголовков metods.h, директория LIBR1), найти корень уравнения с заданной точностью Eps методом хорд, исследовать скорость сходимости и обусловленности метода.

Для данной работы, как и для лабораторной работы №3 задаются индивидуальные варианты нелинейных уравнений (см. подраздел 3.6).

Порядок выполнения лабораторной работы №4:

1) Графически или аналитически отделить корень уравнения (т.е. найти отрезки [Left, Right], на которых функция удовлетворяет условиям применимости метода).

2) Составить подпрограмму - функцию вычисления функции , предусмотрев округление значений функции с заданной точностью Delta с использованием программы Round.

3) Составить головную программу, вычисляющую корень уравнения и содержащую обращение к подпрограмме f(x), HORDA, Round и индикацию результатов.

4) Провести вычисления по программе. Теоретически и экспериментально исследовать скорость сходимости и обусловленность метода.

В подразделе 3.7 приводится текст программы - функции HORDA, предназначенной для решения уравнения методом хорд.

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

(Лабораторная работа № 5)

 

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

Метод Ньютона допускает простую геометрическую интерпретацию (рис. 2). Если через точку с координатами провести касательную, то абсцисса точки пересечения этой касательной с осью Ох будет очередным приближением x_n+1 корня уравнения .

Для оценки погрешности n-го приближения корня предлагается пользоваться неравенством

где М₂-наибольшее значение модуля второй производной на отрезке [a,b]; m₁-наименьшее значение модуля первой производной на отрезке [a,b]. Таким образом, если то Это означает, что при хорошем начальном приближении корня после каждой итерации число верных десятичных знаков в очередном приближении удваивается, т.е. процесс сходится очень быстро (имеет место квадратическая сходимость). Из указанного следует, что при необходимости нахождения корня с точностью e итерационный процесс можно прекращать, когда

(3.1)

Рассмотрим один шаг итераций. Если на (n-1)-м шаге очередное приближение x_n-1 не удовлетворяет условию окончания процесса, то вычисляются величины и следующие приближение корня При выполнении условия (3.1) величина x_n принимается за приближенное значение корня с, вычисленное с точностью e.

В лабораторной работе № 5 предлагается, используя программы-функции NEWTON и ROUND из файла methods.cpp (файл заголовков methods.h, директория LIBR1), найти корень уравнения с заданной точностью Eps методом Ньютона, исследовать скорость сходимости и обусловленность метода.

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

Порядок выполнения лабораторной работы №5.

1) Графически или аналитически отделить корень уравнения (т.е. найти отрезки [Left, Right], на котором функция удовлетворяет условиям сходимости метода Ньютона).

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

3) Составить головную программу, вычисляющую корень уравнения и содержащую обращение к подпрограммам, , (x), Round, NEWTON и индикацию результатов.

4) Выбрать начальное приближение корня x₀ из [Left, Right] так, чтобы >0.

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

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

 

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

(Лабораторная работа №6)

 

Метод простых итераций решения уравнения состоит в замене исходного уравнения эквивалентным ему уравнением x=j(x) и построении последовательности x_n+1=j(x_n), сходящейся при n®¥ к точному решению. Достаточные условия сходимости метода простых итераций формулируются теоремой, приведенной [1,2,7].

Рассмотрим один шаг итерационного процесса. Исходя из найденного на предыдущем шаге значения x_n-1, вычисляется y= j(x_n-1). Если , то полагается x_n=y и выполняется очередная итерация. Если же , то вычисления заканчиваются и за приближенное значение корня принимается величина x_n=y. Погрешность результата вычислений зависит от знака производной : при >0 погрешность определения корня составляет qe/1-q, а при <0 погрешность не превышает e. Здесь q- число, такое, что ½ ½£q<1 на отрезке [a,b]. Существование числа q является условием сходимости метода в соответствии с отмеченной выше теоремой.

Для применения метода простых итераций определяющее значение имеет выбор функции в уравнении , эквивалентном исходному. Функцию необходимо подбирать так, чтобы ½ ½£q<1. Это обусловливается тем, что если <0 на отрезке [a,b], то последовательные приближения x_n=j(x_n-1) будут колебаться около корня c, если же >0, то последовательные приближения будут сходиться к корню c монотонно. Следует также помнить, что скорость сходимости последовательности {x_n} к корню c функции тем выше, чем выше число q.

В лабораторной работе № 6 предлагается, используя программы-функции ITER и Round из файла methods.cpp (файл заголовков methods.h, директория LIBR1), найти корень уравнения с заданной точностью Eps методом итераций, исследовать скорость сходимости и обусловленность метода.

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

Порядок выполнения лабораторной работы №6 должен быть следующим.

1) Графически или аналитически отделить корень уравнения .

2) Преобразовать уравнение к виду так, чтобы в некоторой окрестности [Left, Right] корня производная удовлетворяла условию ½ ½£q<1. При этом следует иметь в виду, что чем меньше величина q, тем быстрее последовательные приближения сходятся к корню.

3) Выбрать начальное приближение, лежащее на [Left, Right].

4) Составить подпрограмму для вычисления значений , , предусмотрев округление вычисленных значений с точностью Delta.

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

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

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

 

3.6. Курсовая работа по дисциплине и варианты заданий

 

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

Задание на курсовую работу по дисциплине "Вычислительная математика".

Используя программы - функции BISECT, NEWTON, HORDA, ITER, Round из файла methods.cpp (файл заголовков methods.h, директория LIBR1), найти корень уравнения с заданной точностью методом бисекции, Ньютона, хорд и итераций соответственно.

Исследуйте обусловленность методов и зависимость числа итераций от точности результата Eps при изменении Eps от 0.0 до 0.000001.

Порядок выполнения курсовой работы

Графически или аналитически отделить корень уравнения (т.е. найти отрезки [Left, Right], на которых функция удовлетворяет условиям применимости методов).

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

Составить головную программу, содержащую ввод исходных данных, обращение к подпрограммам BISECT, NEWTON, HORDA, ITER вывод результатов.

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

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

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

Вид функции определяется вариантом задания. Эти же варианты могут использоваться при выполнении лабораторных работ №№3-6 по отдельности.

№ п/п		№ п/п
	;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;
	;		;

Численное интегрирование

Библиографический список

 

1. Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров: Уч.пособие.- М.: Высш.шк., 1994. - 544 с.

2. Бахвалов Н.С., Жидков Н.О., Кобельков Г.М. Численные методы. - М.: Наука, 1987. - 600 с.

3. Березин И.С., Жидков Н.П. Методы вычислений. Т.1.- М.: Наука, 1966. - 632.

4. Демидович Б.П., Марон И.А. Основы вычислительной математики. - М.: Наука, 1970. - 664 с.

5. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. - М.: Наука, 1972. - 367 с.

6. Марчук Г.И. Методы вычислительной математики. - М.: Наука, 1989. - 608 с.

7. Плис А.И., Сливина Н.А. Лабораторный практикум по высшей математики: Учеб. Пособие для втузов. - 2-е изд. - М.: Высш.шк., 1994. - 416 с.

8. Самарский А.А., Гулин А.В. Численные методы. - М.: Наука, 1989. - 432 с.

9. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений/Пер. с англ. - М.: Мир, 1980. - 279 с.

10. Хемминг Р. Численные методы/Пер. с англ. - М.: Наука, 1972. - 400 с.

11. Сборник задач по структурному программированию: Учеб. пособие/С.А. Ивановский, Ю.Е. Прокофьев, А.В. Смольянинов / Под ред. В.И. Тимохина. - Л.: ЛЭТИ, 1987. - 64 с.

12. Воробьева Г.Н., Данилова А.Н. Практикум по численным методам. - М.: Высш.шк, 1979. - 184 с.

13. Волков Е.А. Численные методы: Учеб. пособие. - М.: Наука, 1982. - 256 с.

14. Основы математического моделирования. Построение и анализ моделей с примерами на языке MATLAB: Учеб. пособие/ Д.Л. Егоренков, А.Л. Фрадков, В.Ю. Харламов; Под ред. А.Л. Фрадкова. - С.-Пб.: БГТУ, 1994. - 192 с.

15. Компьютерная математика. Методич. указ. к лаборат. работам/Сост. И.А. Назаров. - С.-Пб.: ГЭТУ, 1993. - 32 с.

Таблица 4.2

 

Содержание

 

ÂÂÅÄÅÍÈÅ...................................................................................................................................................................................................

1. ÎÑÎÁÅÍÍÎÑÒÈ ÌÀØÈÍÍÎÉ ÀÐÈÔÌÅÒÈÊÈ, ÒÎ×ÍÎÑÒÜ ÂÛ×ÈÑËÅÍÈÉ ÍÀ ÝÂÌ............................................................................

(Ëàáîðàòîðíàÿ ðàáîòà ¹1)................................................................................................................................................................

2. ÈÇÓ×ÅÍÈÅ ÏÎÍßÒÈß ÎÁÓÑËÎÂËÅÍÍÎÑÒÈ ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÇÀÄÀ×È.................................................................................

(Ëàáîðàòîðíàÿ ðàáîòà ¹2)...............................................................................................................................................................

3. ÐÅØÅÍÈÅ ÍÅËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉ............................................................................................................................................

3.1. Îáùèå ñâåäåíèÿ..........................................................................................................................................................................

3.2. Ìåòîä áèñåêöèè...........................................................................................................................................................................

(Ëàáîðàòîðíàÿ ðàáîòà ¹3)..............................................................................................................................................................

3.3. Ìåòîä õîðä.......................................................................................................................................................................................

(Ëàáîðàòîðíàÿ ðàáîòà ¹4)..............................................................................................................................................................

3.4. Ìåòîä Íüþòîíà.................................................................................................................................................................................

(Ëàáîðàòîðíàÿ ðàáîòà ¹ 5).............................................................................................................................................................

3.5. Ìåòîä ïðîñòûõ èòåðàöèé.......................................................................................................................................................

(Ëàáîðàòîðíàÿ ðàáîòà ¹6)..............................................................................................................................................................

3.6. Êóðñîâàÿ ðàáîòà ïî äèñöèïëèíå è âàðèàíòû çàäàíèé.........................................................................................

3.7. Ïðîãðàììû äëÿ ðåøåíèÿ íåëèíåéíûõ óðàâíåíèé.........................................................................................................

4. ×ÈÑËÅÍÍÎÅ ÈÍÒÅÃÐÈÐÎÂÀÍÈÅ.......................................................................................................................................................

4.1. Ñîñòàâíûå ôîðìóëû ïðÿìîóãîëüíèêîâ, òðàïåöèé, Ñèìïñîíà..................................................................................

(Ëàáîðàòîðíàÿ ðàáîòà ¹6)..............................................................................................................................................................

4.2. Ôîðìóëà Ãàóññà. (Ëàáîðàòîðíàÿ ðàáîòà ¹7)...............................................................................................................

Áèáëèîãðàôè÷åñêèé ñïèñîê........................................................................................................................................................

 

ВВЕДЕНИЕ