Растровое представление отрезка. Алгоритм Брезенхейма

Рассм. задачу построения растр. образа отрезка соединяющего точки A(xa,ya) и B(xb,yb). будем считать что xb-xa>=0, yb-ya>0 тогда отрезок записывается ур-ем

Y=ya+(yb-ya) (x-xa), x Є [xа,xb]

хb-xa

Или y=kx+b где k=(yb-ya)/(xb-xa), B=ya-kxa

При этом вычисления можно упростить если использовать рекур. выраж-е, т.к. при увеличении x на 1 y увеличится на к. Но иногда возникают ошибки вычисления, которые портят вид. Для того, чобы этого избежать исп-ся алгоритм, основ. на том, что из 2 кандитатов (пикселов располож. друг над другом) выбирают лежащий ближе к матем.прямой, для этого сравнивают дробную часть с ½.

Пусть x0=xa,y0=ya, xn=xb,yn=yb, yi=k*xi+b, обозначим через ci={kxi+b} дробную часть, тогда если ci<=1/2 yi=[k*xi+b] иначе yi=[k*xi+b]+1

Рассмотри переход к следующей точке

Yi=[k*xi+b]+c

Yi+1=[k*xi+b]+c+k

Ci+1=ci+k

Если ci+k<=1/2 то положим y_i+1=y_i, иначе y_i+1=y_i+1 и c_i+1=c_i-1

Сравнение с 0 более быстрая операция в процессорах поэтому введем переменную di=2сi-1.

Численные методы решения задачи Коши.

Рассм. обыкн. диф. ур-е y’=f(x,y) (1) c нач. усл. y(x₀)=y_{0 .}(2)Реш-е диф. ур-я (1)с нач. усл (2) наз-ся задачей Коши для обыкн. диф. ур-я. Если ф-ция f(x,y) диффренц. в окр. т (x₀,y₀) непрерыв. вместе с частн. произв f’_y (x,y) то зад. Коши имеет единств. реш-е. Рассм. 2 группы методов для реш-я задачи Коши: одношаговые - позволяют нах-ть реш-е диф. ур-я в некоторой точке отрезка, исп.информац. лишь об одной пред. точке. К этим мет. относ.мет. Эйлера, Рунге- Кутта. Многошаговые - позволяют нах-ть реш. диф. ур-я в некотор. точке отрезка, исп. информац. о решениях в некотор. предыдущ. точках. Метод Адамса.

Метод Эйлера. Пусть дано ур-е (1) с нач. усл-ем (2). Выбирая шаг h, построим, начиная с т. x₀ систему равноотст. точек x_i=x₀+ih (i=0,1,..) Вместо искомой инт. кривой на отр. [x0,x1]рассм. отрезок. касательной к ней в т. L₀(x₀,y₀), ур-е котор. имеет вид: y=y₀+f(x₀,y₀)(x-x₀). При х=х₁ из ур-я касат. получаем y₁=y₀+hf(x₀,y₀). След-но, приращ. ф-ции на 1-м шаге: Δy₀=hf(x₀,y₀). Проведем аналогич. касат. к инт. кривой в т. L₁(x₁,y₁), ур-е котор. имеет вид y=y₁+f(x₁,y₁)(x-x₁). При х=х₂ из ур-я касат: y₂=y₁+hf(x₁,y₁).След-но приращ ф-ции на втором шаге Δy₁=hf(x₁,y₁). Т.о. вычисл. табл. знач-й ф-ции, являющ. реш-ем диф. ур-я (1) состоит в послед. вычислении по ф-лам: Δy_k=hf(x_k-₁,y_k-₁), y_k+1=y_k. Вычислим погреш. мет. Эйл. на каждом шаге. Найдем локал. погреш., присутств. на каждом шаге, котор. опред-ся разностью между точн. знач-ем ф-ции и соотв. знач-ем касат. На 1-м шаге: Δ=y(x₁)-(y₀+hf(x₀,y₀))=y(x₀+h)-(y₀+hf(x₀,y₀))= y₀₊ y’(x₀)h+ y’’(x₀)h²/2!+...-(y₀+hf(x₀,y₀))=y’’(x₀)h²/2!. Из этой ф-лы видно, что локал. погреш. пропорц h². Суммар. погреш. после N ходов пропорц NO(h²).

Метод Эйл-Коши Известно много различ уточнений метода Эйлера. Они заключ-ся в уточнении направления перехода от точки (x_i,y_i) к точке (x_i+1,y_i+1). В методе Эйл-Коши исп-ся след порядок вычисл-я: y*_i+1=y_i+hf(x_i,y_i); y_i+1=y_i+h[f(x_i,y_i)+f(x_i+1,y*_i+1)]/2 (1) Геометрически это означает, что опред-ся направление интегр кривой в исход точке (x_i,y_i) и во вспомогат точке f(x_i+1,y*_i+1) и в качестве окончат берётся среднее знач-е этих направлений.В рассмотр случае логично исп-ть метод простой итерации, поскольку нелинейное ур-е уже разрешимо относительно y_i+1. Тогда, если номер итерации обозначить верхним индексом, итерац процесс запишется в виде: y^(k+1) _i+1= y_i+h[f(x_i,y_i)+f(x_i+1,y^k _i+1)]/2 В качестве y⁽⁰⁾ _i+1 можно принять либо y₁, либо y⁽⁰⁾ _i+1 =y_i+hf(x_i,y_i), т.е. использовать знач-е вычисленное по фор-ле Эйлера. В этом случае в первой итерации имеем y⁽¹⁾ _i+1 =y_i+h[f(x_i,y_i)+ f(x_i+1,y_i+hf(x_i,y_i)]/2(3) Эта ф-ла наз-ся ф-лой Эйлера с пересчётом. Подобные схемы называются схемами типа прогноз-корректор. Сначала по формуле Эйлера нах-ся приближ знач-е, а затем по фор-ле (3) уточняется это реш-е.Метод Эйлера с пересчётом обладает третьим порядком точности на шаге.

Метод Рунге-Кутта.

метода Рунге-Кутта 4 порядка. Искатьреш-е будем в виде

Погрешность метода Рунге-Кутта оценить очень сложно. Чаще используют приближение с вдвое меньшим шагом.

2.Любым методом решить систему .

Метод исключения переменной.

Решение лин. неоднород. ур-я ищется в виде , где -общ. реш-е однород ур-я y1’’+y1=0, а у*- какое-нибудь частное реш-е неоднород. Составим характеристич.ур-е:

Теорема. Если y1(x) и y2(x) явл-ся соответственно частными решениями ур-й

y’’+p(x)y’+q(x)y=f1(x) и y’’+p(x)y’+q(x)y=f2(x), то y=y1(x)+y2(x) есть частное реш-е ур-я y’’+p(x)y’+q(x)y=f1(x)+f2(x)

Найдём частное решение уравнения y₁’’+y₁=t+e^t. Реш-е будем искать в в виде суммы y1**+y1*** где у1** -частн реш-е ур-я у1’’+y1=t, a y1***- частн реш-е ур-я y1’’+y1= e^t.

Найдем частн. реш-е у1’’+y1=t. в виде у1**=t^se^αtQ_n(x) –метод неопределенных коэфф., т.к. правая часть спец. вида f(t)= e^αtP_n(t),где α=0,n=1, s=0. Т.о. у1** ищется виде многочл 1-й степени у1**=at+b. Подставив у1** в исход. ур-е, получим at+b=t. Приравниваем коэфф. при одинак степ. t -> a=1, b=0 -> y1**=t

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

Тогда частное решение исходного уравнения:

.

Билет 2

3.Вывод ур-я Эйлера для ф-ла

Ф-лом в лин. нормир. пр-ве Е наз-ся ф-ция F, определен. на всем Е или на некотор. его подмн-ве и принимающ. веществ. знач-я. Опр Пусть F- ф-л, опред. в лин. нормир. пр-ве Е. Если в некотор. точке Е ф-ция F( +th) переменного t дифференцир.при t=0 h E, то ее производная наз-ся первой вариац. ф-ла F в т. вдоль вектора h и обознач. δF(,h).

Рассм. ф-л (1), где у=у(х) и f(x,y,y’) - ф-ция, имеющая непрерыв.частные производные до второго порядка включит. на мн-ве --- <y<+ , - < y ’<+ . Найдем вариацию ф-ла (1). По опред.

Значит,

(2).Найдем стационар. точки ф-ла (1) на мн-ве

Ф-ции h в (2) при этом должны удовлетворять условиям h(a)=h(b)=0 (3)

Действительно, так как y, y+h E' то y(a)=A, y(b)=B, y(a)+h(a)=A, y(b)+h(b)=B откуда получаем условия (3). Преобразуем (2). Для этого второе слагаемое проинтегр. по частям. С учетом условий (3) получим

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

Для стационар. точек должно выполняться усл. δF(y,h)=0, откуда следует рав-во

(4) для любой ф-ции h, удовлетворяющей усл. (3). В силу основной леммы вариац. исчисления из (4) следует, что

Ур-е Эйлера для ф-ла (1) при краевых условиях y(a)=A, y(b)=B.

или, в развернутой форме,

Итак, для нахождения экстремалей ф-ла (1), проходящих через точки (a,A) и (b,B), нужно искать реш-е ур-я Эйлера,удовлетв. краевым условиям y(a)=A, y(b)=B.

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

Частные случаи:

1. Пусть функция f в (1) не зависит от y: f=f(x,y’). Тогда ур-е Эйлера имеет вид

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

2. Пусть функция f зависит только от y’:f=f(y’). Ур-е Эйлера имеет вид откуда y’’=0, или =0 Экстремалями в этом случае являются всевозможные прямые

3. Пусть f не зависит от y’ f=f(x,y), тогда ур-е Э примет вид .Реш-е получ. ур-я не зависит от постоянн и не удовл. краевым усл.-> реш-я не сущ.

4. Пусть f не зависит от х, тогда ур-е примет вид т.к. , откуда для экстрем получ. диф. ур-е: f-

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: