이차원 이분 격자법
어떠한 영역에 임의로 수평, 수직으로 일정한 간격의 선을 긋는다는 것은 여러 격자로 볼 수 있다. 그리고 나누어진 선 각각에 대하여 그 선을 기준으로 영점 교차에 대한 이분법이 행해진다. 이로서 함수의 궤적은 그래프 상에 찍힌, 즉 분할된 사각형의 변에 찍힌 점들을 연결하여 구할 수 있다.
이러한 임의로 그러진 선들 각각에 대해 이분법을 행해서 얻어진 점들을 영점이라고 한다. 이때 임의로 정한 영역을 수평, 수직으로 나누는 선들은 이이 함수의 궤적을 비교적 정확히 찾아내기 위하여 영점 교차들이 적합한 간격을 유지하도록 설정한다. 또 이 선들과 만나지 않는 함수의 부분은 검출되지 않는다.
<수식>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define inv 0.05
#define error 0.0001
double funct(double x, double y);
void bisx(double y, double xl, double xh, double yl, double yh) {
double f_out_1, f_out_2, inv_temp, x;
inv_temp = inv;
x = xl;
f_out_1 = funct(x, y);
while (1)
{
f_out_2 = funct(x, y);
if (f_out_1 * f_out_2 < 0.) {
if (inv_temp < error) {
printf("\n\t %lf\t %lf\t %lf", x,y,inv_temp);
break;
}
else {
x -= inv_temp;
inv_temp /= 2;
}
}
x += inv_temp;
if (x > xh)break;
}
}
void bisy(double x, double xl, double xh, double yl, double yh) {
double f_out_1, f_out_2, inv_temp, y;
inv_temp = inv;
y = yl;
f_out_1 = funct(x, y);
while (1)
{
f_out_2 = funct(x, y);
if (f_out_1 * f_out_2 < 0.) {
if (inv_temp < error) {
printf("\n\t %lf\t %lf\t %lf", x, y, inv_temp);
y += inv;
break;
}
else {
y -= inv_temp;
inv_temp /= 2.;
}
}
y += inv_temp;
if (y > yh)break;
}
}
double funct(double x, double y) {
double out;
out = 3. * sin(3. * x) + 4. * cos(3. * y);
return out;
}
int main(void) {
double xl, xh, yl, yh, x, y;
/*initialization*/
xl = 0., xh = 1.;
yl = 0., yh = 1.;
/*headline output*/
printf("\n-------- Bisection Method for two veriables ----------\n");
printf("\n\t x\t\t y\t\t F(x,y)\n");
/*Bisection method*/
y = yl;
while (1)
{
bisx(y, xl, xh, yl, yh);
if (y > yh)break;
else {
y += inv;
continue;
}
}
x = xl;
while (1)
{
bisy(x, xl, xh, yl, yh);
if (x > xh)break;
else {
x += inv;
continue;
}
}
_getch();
}
세밀한 이차원 이분 격자법
일반적으로 영점 교차 위치가 발견된 사격형 부분만을 더 작은 사각형으로 나누어 검색하는 것은 애초에 세말한 사각형으로 분할하여 검색하는 것보다 빠르고, 작은 용량으로도 가능하다
<수식>
#include <stdio.h>
#include <math.h>
#include <conio.h>
double funct(double, double);
int main(void)
{
int i, j, dim, num = 50, l[100][100];
double xl = 1.0, yl = 1.0, x, y, c, a[100][100], f_out;
printf("\nLower Left Coordinates o fSquares are\n");
printf("Input the Lower Value of x-axis for Search :");
scanf_s("%lf", &xl);
printf("Input the Lower Value of x-axis for Search :");
scanf_s("%lf", &yl);
printf("Input the Number of Grid Divisions :");
scanf_s("%d", &num);
printf("\n=========================================================================\n");
printf("Lower Left Corrdinates of Squares are\n");
printf("\t x\t\t y\n");
dim = 2;
c = (double)dim / (double)num;
/*algorithem 1*/
for (i = 1; i <= num + 1; i++)
{
for (j = 1; j <= num + 1; j++)
{
x = xl + c * (double)(i - 1);
y = yl + c * (double)(j - 1);
f_out = funct(x, y);
a[i][j] = f_out;
l[i][j] = 0;
}
}
for (i = 1; i <= num + 1; i++)
{
for (j = 1; j <= num + 1; j++)
{
if (a[i][j] == 0.0)
/*algorithem 2a*/
{
l[i + 1][j + 1] = 1;
l[i][j + 1] = 1;
l[i + 1][j] = 1;
l[i][j] = 1;
}
if (a[i][j] * a[i + 1][j] < 0.0)
/*algorithem 2b*/
{
l[i + 1][j + 1] = 1;
l[i + 1][j] = 1;
}
if (a[i][j] * a[i][j + 1] < 0.0)
/*algorithem 2c*/
{
l[i + 1][j + 1] = 1;
l[i][j + 1] = 1;
}
}
}
/*output printout*/
for (i = 1; i <= num; i++)
{
for (j = 1; j <= num; j++)
{
if (l[i + 1][j + 1] == 1)
{
x = xl + c * (double)(i - 1);
y = yl + c * (double)(j - 1);
printf("\t%lf\t%lf\n", x, y);
}
}
}
printf("\nSquare Dimension is %lf", c);
_getch();
}
double funct(double x, double y)
{
double out;
out = (x - 1.) * (x - 1.) + (y - 1.) * (y - 1.) - 1.;
return out;
}
영점 곡선의 추적
구하는 함수의 일부분만을 먼저 구하고, 이 일부분의 선을 함수의 궤적에 맞도록 추적해 나가는 방법이다. 넓은 영역에서 그래프 위의 점들을 동시에 찾아내는 것이 아니라 한 점을 먼저 찾고 순차적으로 이 점을 기준으로 다음 점을 또 그다음 점을 순차적으로 찾아 나가는 것이다. 그리고 이미 발견된 점들을 이용하여 다음 점을 찾는 수직선을 탐색선이라고 한다.
<수식>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
#define ESC 27
#define SQ(X)((X)*(X))
#define inv 0.1
#define error 0.000001
#define clrscr() == system("cls")
void root(double, double);
double funct(void);
double x, y;
int main(void) {
double a, w, u, v, b, d, p, q;
a = 0., w = 0.1;
system("cls");
printf("\n\nPress any key to continur...... or Press ESC\n");
printf("\n=============== Zero Curve Tracking ===============\n");
printf("\n\t x\t\t y\n\n");
x = a;
p = inv, q = 0.0;
root(p, q);
printf("\t%8.5lf\t %8.5lf\n", x, y);
u = x, v = y;
x = a, y += w;
p = inv;
root(p, q);
printf("\t%8.5lf\t %8.5lf\n", x, y);
while (1)
{
d = sqrt(SQ(x - u) + SQ(y - v));
a = (x - u) / d;
b = (y - v) / d;
u = x;
v = y;
x += fabs(w) * (a - b);
y += fabs(w) * (a + b);
p = inv * b;
q = -inv * a;
root(p, q);
printf("\t%8.5lf\t %8.5lf\t\n", x, y);
if (_getch() == ESC)
exit(0);
else continue;
}
}
void root(double p, double q) {
double f_out_1, f_out_2;
f_out_1 = funct();
while (1) {
x += p;
y += q;
f_out_2 = funct();
if (f_out_1 * f_out_2 <= 0.0)
{
if (fabs(p) > error || (fabs(q) > error))
{
x -= p;
y -= q;
p /= 2.;
q /= 2.;
}
else break;
}
else f_out_2 = f_out_1;
}
}
double funct() {
double out;
out = SQ(x) + SQ(y) - 4;
return out;
}
이차원 경사도 탐색법
함수에서 가장 내부의 곡선이 최소값을 갖는다면 내부의 곡선을 찾아 나가는 방법을 동고선과 이차원 함수에서 보여준다. 대체로 가장 크게 증가하는 기울기의 방향과 크기는 함수의 편미분인 경사도가 된다. 따라서 가장 크게 감소하는 기울기의 방향과 크기는 경사도에 음의 값을 취한 함수가 된다. 경사도는 항상 임의 곡선의 임의 점에서 그 곡선에 수직인 직선이 되는 성질을 갖는다. 이 성절을 이용해서 함수의 최솟값을 구할 수 있다.
<수식>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define SQ(X) ((X)*(X))
#define converge 0.25
#define error 0.00001
double funct(double, double);
double df_dx(double);
double df_dy(double);
void main(void) {
double f_out, f_out_1, f_out_2, x = 0.0, y = 0.0;
printf("\n====== Relative Minimum Using the Gradient======\n");
printf("\nEnter the Initial value of x-axis :");
scanf_s("%lf", &x);
printf("\nEnter the Initial value of y-axis :");
scanf_s("%lf", &y);
printf("\nCoordinates of Minimum===============");
while (1) {
f_out_1 = df_dx(x);
f_out_2 = df_dy(y);
if (sqrt(SQ(f_out_1) + SQ(f_out_2)) < error) {
printf("\nx=%lf", x);
printf("\ny=%lf", y);
f_out = funct(x, y);
printf("\n\nThe value of this function at this point:%lf\n", f_out);
break;
}
x -= converge * f_out_1;
y -= converge * f_out_2;
}
_getch();
}
double funct(double x, double y) {
double out;
out = x * x - 4. * x + y * y - 6. * y + 11.;
return out;
}
double df_dx(double x) {
double out;
out = 2. * x - 4.;
return out;
}
double df_dy(double y) {
double out;
out = 2. * y - 6.;
return out;
}
수치 미분을 사용한 방법
경사도 탐색에 필요한 편미분에 수치 근사법을 사용한 방법
<수식>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define SQ(X)((X)*(X))
#define converge 0.25
#define error 0.00001
#define inv 0.001
float funct(float, float);
void main(void) {
float g, h, s, x = 0.0, y = 0.0, f_out;
printf("\n====== Gradie Search Using Numerical Derivatives ======");
printf("\nEnter the Initial Value of x_axis :");
scanf_s("%f", &x);
printf("\nEnter the Initial Value of y_axis :");
scanf_s("%f", &y);
printf("\nCoordinates of Minumum===============");
while (1) {
f_out = funct(x, y);
s = f_out;
x += inv;
f_out = funct(x, y);
g = (f_out - s) / inv;
x -= inv;
y += inv;
f_out = funct(x, y);
h = (f_out - s) / inv;
y -= inv;
if (sqrt(SQ(g) + SQ(h)) < error)
{
printf("\nx=%f", x);
printf("\ny=%f", y);
f_out = funct(x, y);
printf("\n\nThe value of this function at this point: %f\n", f_out);
break;
}
x -= converge * g;
y -= converge * h;
}
_getch();
}
float funct(float x, float y) {
float out;
out = x * x - 4. * x + y * y - 8. * y + 12.;
return out;
}
가파른 경사법
경사도의 크기에 비례하는 수치를 갖는단계를 취하는 대신에 제어 수치를 갖는 더 작은 단계들로 구성된다
<수식>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define SQ(X)((X)*(X))
#define error 0.00001
float funct(float, float);
void main(void) {
float f_out, inv, dx, dy, x = 0.0, y = 0.0, s, p;
printf("\n====== Steepst Descent To Find Minima========");
printf("\nEnter teh Initial value of x_axis :");
scanf_s("%f", &x);
printf("\nEnter teh Initial value of y_axis :");
scanf_s("%f", &y);
printf("\nCoordinates of Minimum===============");
inv = 1.0;
while (1) {
dx = 2. * x - 4.;
dy = 2. * y - 8.;
s = sqrt(SQ(dx) + SQ(dy));
if (s < error) {
printf("\nx=%f", x);
printf("\ny=%f", y);
f_out = funct(x, y);
printf("\n\nThe value of this function at this point: %f\n", f_out);
break;
}
else {
f_out = funct(x, y);
while (1) {
p = f_out;
x -= inv * dx / s;
y -= inv * dy / s;
f_out = funct(x, y);
if (f_out >= p)
break;
}
inv /= 2.;
}
}
_getch();
}
float funct(float x, float y) {
float out;
out = x * x - 4. * x + y * y - 8. * y + 10.;
return out;
}'학교수업, CS > 수치해석' 카테고리의 다른 글
| 최소 자승법(촐레스키법을 이용한 행렬의 제곱근) (0) | 2022.11.30 |
|---|---|
| 고유치(파데브-레브리어의 알고리즘) (0) | 2022.11.30 |
| 행렬&역행렬 (0) | 2022.11.30 |
| 연립방정식(가우스 조단의 피보팅, 가우스 자이달 방법) (1) | 2022.11.30 |
| 방정식&함수(이분법, 뉴튼랩슨법, 할선법, 가상위치법, 중근, 극값) (0) | 2022.11.30 |