Размещено на http://www.allbest.ru/

КОНТРОЛЬНАЯ РАБОТА

на тему: «Метод половинного деления»

Содержание

Введение

1. Изучение методов структурного программирования

1.1 Метод простых итераций (последовательных приближений).

1.2 Метод релаксаций

1.3 Метод Ньютона (касательных)

1.4 Метод секущих

1.5 Метод хорд

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

3. Задача

Заключение

Список использованных источников

Введение

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

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

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

1. Изучение методов структурного программирования

Методы приближенного решения уравнений вида f(x)=0 (f непрерывна)

Псть задана функция f(x) и требуется найти корни уравнения

вычисление половинное деление корень уравнение

f(x) = 0 (1)

Эта задача разделяется на два этапа:

- локализация корней, т.е. нахождение таких отрезков на оси X, на каждом из которых находится только один корень;

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

Для решения задачи локализации корней нет каких-либо рекомендаций, кроме утверждения о том, что если на концах некоторого отрезка [a,b] функция f(x) имеет разные знаки т.е. f(a)? f(b)>0 и монотонна, т.е. f '(x) не меняет знак при x? [a,b], то на отрезке [a,b] имеется единственный корень уравнения (1).

При решении практических задач очень часто отрезок [a,b], содержащий требуемый корень известен заранее.

Далее будем рассматривать методы решения задачи о нахождении корня уравнения (1) принадлежащего заданному отрезку [a,b] с заданной степенью точности.

1.1 Метод простых итераций (последовательных приближений).

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

Представим уравнение (1) в виде

x=s(x). (2)

Это можно сделать, например, прибавив x к обеим частям уравнения (1). Очевидно, что при подстановке искомого корня x* в уравнение (2) оно превращается в тождество x* ? s(x*).

Рассмотрим последовательность чисел x_i , которая определяется следующим образом: x_{0 ?} [a,b] - задано, x_k+1 = s(x_k) .

При некоторых определенных свойствах функции s(x) эта последoвательность сходится к искомому корню, т.е. x_k? x^* при k? ? .

Метод простых итераций имеет следующую наглядную геометрическую интерпретацию (см. рис.1).

Решением уравнения (2) будет абсцисса точки пересечения прямой y=x с кривой y=s(x). При выполнении итераций значение функции s(x) в точке x_i необходимо отложить по оси абсцисс.

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

Рисунок 1

Достаточные условия сходимости формулируются в теореме.

Теорема. Пусть в шаровой окрестности радиусом r некоторой точки ? U_r(?) = |x-?| ? r функция s(x) удовлетворяет условиям

1) Коши-Липшица: для любых x₁,x₂ ? U_r(?)

| s(x₁) - s(x₂) | ? q |x₁ - x₂| , причем q=const<1; (4)

2) |s(?) - ?| ? (1-q)? r .

Тогда уравнение (1) имеет на U_r(?) единственный корень x^*, последовательность (3) сходится к x^* при любом x₀ ? U_r(?), а для погрешности справедлива оценка |x_k - x^*| ? q^k |x₀-x^*| .

На практике в качестве рассматриваемой окрестности U_r(?) рассматривают интервал [a,b], а вместо условия (4) обычно требуют выполнения менее сильного условия |s'(x) | ? q <1.

Условие (5) гарантирует что, все вычисляемые итерации x_k будут принадлежать окрестности U_r(?), но при решении практических задач доказать выполнение этого условия невозможно, тем более, что интервал поиска [a,b] не совпадает с интервалом U_r(?). В итоге можно столкнуться с ситуацией, когда на отрезке [a,b] выполнено условие (7), но уже x₁ выходит за границы интервала [a,b] и метод итераций расходится. Для таких случаев можно рекомендовать каким-либо образом сузить интервал локализации из которого выбирается начальное приближение. Такой подход обосновывается следующим следствием.

Следствие. Пусть в окрестности некоторой точки U_r(?) функция s(x) удовлетворяет условию Коши-Липшица (4) и известно, что x^*? U_r(?), тогда существует такая окрестность U? U_r(? ) содержащая искомый корень x^*? U, что если выбрать x_0? U, то последовательность (3) сходится к корню x^* и имеет место оценка (6).

Скорость сходимости последовательности (3) такова, что на каждом шаге погрешность убывает в q раз |x_k+1-x^*| ? q |x_k-x^*| такая сходимость называется линейной. Используя это неравенство можно получить оценку числа итераций, необходимых для достижения заданной точности.

qⁿ|x₀-x^*| ? ? .

Мажорируя неизвестную величину |x₀-x^*| размером интервала [a,b] получим

.

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

s(x) = f(x) + x.

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

1.2 Метод релаксаций

Умножим уравнение (1) на некоторое число ? =const? 0 и применим к нему метод простых итераций

? ? f(x)=0;

x = ? ? f(x)+x = s(x);

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

x₀ ? [a,b] задано, x_k+1 = ? f(x_k) + x_k .

Подберем параметр ? так, чтобы выполнялось условие сходимости

|s'(x)| = |? f '(x)+1| ? 1,

откуда получаем

? f '(x) < 0 , ? > -2/f '(x).

1.3 Метод Ньютона (касательных)

Зададим некоторое начальное приближение x_0? [a,b] и линеаризуем функцию f(x) в окрестности x₀ с помощью отрезка ряда Тейлора

f(x) = f(x₀) + f '(x₀) (x-x₀).

Вместо уравнения (1) решим линеаризованное уравнение

f(x₀) + f '(x₀)(x-x₀) = 0,

трактуя его решение x как первое приближение к корню

x₁ = x₀ - f(x₀)/f '(x₀) .

Продолжая этот процесс, приходим к формуле Ньютона

x_k+1 = x_k - f(x_k)/f '(x_k)

которую можно считать итерационным процессом с итерирующей функцией s(x) = x - f(x)/f '(x).

Геометрическая интерпретация этого процесса показана на рис.2. Уравнение (9) является уравнением линии касательной к кривой f(x) в точке x₀, поэтому этот метод называют методом касательных.

Рисунок 2

Сходимость метода Ньютона оценивается неравенством

|x_k+1 - x*|? |x_k-x*|² M₂/m₁

Где

M₂ = max |f "(x)| , m₁= 2 min |f '(x)| , x? [a,b].

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

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

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

x_k+1 = x_k - f(x_k)/f '(x₀).

Этот метод также можно считать методом релаксаций с параметром

? = -1/f '(x₀).

Сходимость этого метода, как и метода релаксаций линейная.

1.4 Метод секущих

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

Это самый простой метод вычисления корня уравнения. Разделим исходный отрезок [a,b] пополам

c=(a+b)/2 .

Проверяя знаки f(a), f(b), f(c) выясним в каком из отрезков [a,c] или [c,b] содержится корень

x* ? [a,c] , если f(a)f(c)<0 ;

x* ? [c,b] , если f(c)f(b)<0 .

Выбранный отрезок принимаем за [a,b] и повторяем это до тех пор пока получаемый отрезок не сожмется до заданной степени точности. При n итерациях получим соотношение

(b-a)/2ⁿ ? ?

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

n? ln₂(b-a)/? .

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

3. Задача

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

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

Какие же факторы принять за существенные в этой задаче? Поскольку речь идет о средневековье, то скорость снаряда и дальность полета невелики. Значит можно считать несущественным, что Земля круглая и пренебречь сопротивлением воздуха. Остается единственный фактор - сила земного притяжения. В этом случае, как вы знаете из физики, горизонтальное (х) и вертикальное (у) смещение снаряда за время t описывается формулами

,

где g - ускорение свободного падения, v - начальная скорость снаряда, б - угол наклона пушки к горизонту. Эти формулы задают математическую модель полета снаряда. Нас же интересует, на какой высоте окажется снаряд, пролетев расстояние S.

Впрочем, это нетрудно найти. Выразим время полета снаряда на расстояние S из первой формулы:

,

и подставим во вторую:

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

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

Мы заранее можем указать «вилку» для угла: 0 и р/4 (мы надеемся, что вы помните какой угол имеет радианную меру р/4 и чему приближенно равно р). А дальше будем делить пополам эту «вилку» и смотреть, куда попадает снаряд, пока не добьемся нужного результата.

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

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

Как же предлагается находить этот корень? А вот так. Делим отрезок [a;b] пополам, т.е. берем середину отрезка, а+b/2. В этой точке вычисляем значение функции f(x). Если это значение 0, то корень найден; если нет, то оно имеет тот же знак, что и значение на одном из концов отрезка [a;b]. Тогда этот конец заменим точкой а+b/2. Новый отрезок тоже содержит корень уравнения f(x)=0, поскольку на его концах функция f(x) снова имеет разные знаки. Однако этот отрезок в 2 раза короче предыдущего. И самое главное - с ним можно поступить точно так же. Со следующим отрезком еще раз проделать то же самое и т.д. поскольку длина отрезка каждый раз уменьшается вдвое, мы можем получить отрезок сколь угодно малой длины, внутри которого содержится корень уравнения f(x)=0. Например, если исходный отрезок был [3;4], т.е. имел длину 1, то через десять шагов мы получим отрезок длиной . Это означает, что концы отрезка дают нам приближенное значение корня с точностью, равной длине отрезка: левый конец отрезка - приближенное значение корня с недостатком, правый конец - приближенное значение корня с избытком.

Фактически мы сейчас сформулировали метод приближенного решения уравнения f(x)=0. Его можно было бы назвать методом артиллерийской пристрелки. Но математики называют его методом половинного деления.

Заключение

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

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

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

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

Список использованных источников

1. Гейн А.Г., А.И. Сенокосов, Н.А. Юнерман «Информатика: учебное пособие для 10-11 классов». М.: Просвещение, 2001.

2. Гейн А.Г., В.Г. Житомирский, Е.В. Линецкий, М.В. Сапир, В.Ф. Шолохович «Основы информатики и вычислительной техники». М.: Просвещение, 1992.

3. Симонович С., Г. Евсеев. «Практическая информатика: Учебное пособие для средней школы. Универсальный курс». - М.: Аст-пресс: Инфорком-пресс, 2001.

4. Сеть Internet

Размещено на Allbest.ru