STEAM R&E 연구결과보고서
(컴퓨터는 방정식을 어떻게 풀까? 적분을 어떻게 할까?)
2016. 11. 30.
부개여자고등학교
< 연구 결과요약 >
과 제 명 - 컴퓨터는 방정식을 어떻게 풀까? 적분을 어떻게 할까?
연구목표
- 방정식의 풀이와 적분을 컴퓨터를 이용하여 수치적으로 접근한다.
- 교과서에 제시되지 않은 다양한 방법으로 수학을 접함으로서 수학의 이해 를 높인다.
- 알고리즘을 프로그래밍을 통하여 구현함으로서 프로그래밍 언어에 대한 이해를 높인다.
- 주어진 문제에서 최적화된 솔루션을 찾아보는 과정을 통하여 최적화 필요 성과 중요성에 대하여 탐구한다.
연구내용
- 방정식의 풀이와 적분을 수치 해석적인 방법으로 어떻게 해결하는지 탐구 한다.
- 수치해석적 접근에서 발생하는 오차에 대하여 이해하고 발생 오차 범위를 계산한다.
- 기존의 수치해석적 접근법에 대한 이해를 마친 후 자신만의 방정식 풀이 법과 적분법을 새롭게 고안한다.
- 새로 고안한 방법의 오차범위를 계산하고 효율성에 대하여 토론한다.
- 기존 방법과 새로운 방법의 계산을 위한 알고리즘을 구상하고, 경제적인 알고리즘으로 만들기 위하여 고민하고 다듬어 나간다.
- 최적의 알고리즘을 찾고 나서 그것을 C언어로 프로그래밍한다.
- 빠르고 효율적인 프로그래밍 기법에 대하여 탐구하고 개선한다.
- 수학축전 등 다양한 방법으로 연구한 내용을 공유한다.
연구성과
-기존의 Brent’s Method에 대한 탐구를 통한 수치해석 방정식 풀이과정 이해 및 탐구
-Brent’s Method를 변형하여 알고리즘을 작성하고 이를 C언어를 통하여 구현함.
-기존의 Simpson 1/3 적분법에 대한 탐구 및 이해 -SImpson 1/3 적분법을 변형하여 개선된 알고리즘 구현
주요어 (Key words)
수치해석, 수치해석 방정식 풀이, 수치해석 적분, 알고리즘, 최적화, C언어, 프로그래밍, 컴퓨터 연산구조
< 연구 결과보고서 >
1. 개요
□ 연구목적
○ 방정식의 풀이와 적분을 컴퓨터를 이용하여 수치적으로 접근한다.
○ 교과서에 제시되지 않은 다양한 방법으로 수학을 접함으로서 수학의 이해를 높인다.
○ 알고리즘을 프로그래밍을 통하여 구현함으로서 프로그래밍 언어에 대한 이해를 높인다.
□ 연구범위
○ 수치해석적인 방정식 풀이와 적분을 탐구하고 개선된 방법을 찾아봄.
○ 기존의 수치해석 방정식 풀이법 중에서 많이 사용되는 Brent’s Method 알고리즘의 일부를 개선하여 비교연구 함.
○ 기존의 수치해석 적분 풀이법 중에서 Simpson 1/3 알고리즘의 일부를 개선하여 비교연 구 함.
2. 연구 수행 내용
□ 이론적 배경 및 선행 연구
Ⅰ. 수치해석 방정식 풀이법 1. Brent's method
수치해석 분야에서, Brent's method 는 복잡하지만 자주 사용되는 방법이다. 이 알고리즘은 이분법, 할선법 그리고 역연산법을 혼합하여 사용한다.
이 방법은 이분법의 신뢰성과 상대적으로 신뢰성은 떨어지지만 수렴속도는 빠른 할선법 또는 역연산법의 장점을 모두 가지고 있다. 기본적으로는 할선법과 역연산법 을 사용하지만 상황에 따라서 이분법을 바꿔 사용하므로 할선법과 역연산법에 내재적 으로 잠재되어있는 발산 또는 수렴속도의 더딤을 해결 할 수 있다. Brent’s method는 Dekker’s method를 개선하여 만들 것이어서 Brent-Dekker method라고 불리기도 한다.
2. Dekker's method
이분법과 할선법을 혼합하여 사용하려는 아이디어는 Dekker의하여 개발되었다.
우리가 방정식 의 해를 구하려 한다고 가정하자. 이분법과 마찬가지고 Dekker 의 방법에서도 초기점 두 개가 필요하다. 이를 와 라고 하자. 이 때,와 는 다른 부호를 가져야 한다. 만약 함수 가 구간 에서 연속이면 사잇값 정리에 의하여 함수 의 근이 구간 에 적어도 하나 존재하게 된다.
모든 추정에서는 세 점이 필요하다. - 는 현재 추정점, 은 이전의 추정점.
-는 상대점. 즉 와 가 다른 부호를 가져서 구간 안에 방정식의 해가 적어도 하나 있어야 한다. 그리고
의 값이
의 값보다 더 작아서 가보다 더 나은 추정이 되어야 한다.
두 개의 값이 먼저 계산이 된다.
≠ 일 때
그 외의 경우
첫 번째 값은 할선법에 의한 값이고, 두 번째 값은 이분법에 의한 값이다. 만약 할선법에 의한 값이 와 사이에 있는 값이라면 가 된다. 그렇지 않은
경우 이 된다.
그 다음에는 과 이 다른 부호가 되도록 을 선택해야 한다. 만약 와 이 부호가 다르다면 이다.
만약 와 이 부호가 같다면 이다.
마지막으로 이라면 이 보다 더 나은 추정이므로 과 의 값을 서로 맞바꾼다.
Dekker의 방법은 일반적으로 좋은 수렴성을 보여주지만 할선법을 사용함에 있어서
의 값이 너무 느리게 수렴하는 경우가 생긴다. 특히
의 값이 아주 작을 때 그런일이 자주 발생한다. 이런 경우 이분법 보다도 더 많은 추정 단계가 필요하기도 하다.Brent는 이 방법의 단점을 보완하고자 수정된 방법을 제시하였다. 할선법의 결과다 다음 추정값으로 사용되기 위한 추가적인 조건을 넣었다. 두 가지 조건을 만족하여야 할선법의 값이 채택되는데,
오차범위가 인 경우,
이전 추정에 이분법이 사용되었다면 부등식
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분 법이 사용된다.
이전 추정에 할선법 또는 역이차법이 사용되었다면
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분 법이 사용된다.
또한 이전 추정에 이분법이 사용되었다면 부등식
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분 법이 사용된다.
이전 추정에 할선법 또는 역이차법이 사용되었다면
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분 법이 사용된다.
이렇게 수정된 방법을 통하여 Brent는 할선법과 역이차법을 사용하였으며 선형적으로 잘 수렴함을 증명하였다.
또한 가 다음 추정으로 채택되기 위한 조건을 조금 수정하여
와 사이에
가 있어야먄 을 로 채택 되로록 하였다.
Ⅱ. 수치해석 적분 풀이법 1. Simpson 1/3 Method
Simpson 1/3 공식은 다항식이 2차인 경우에 해당되며 함수의 세 점을 이용하여 함수를 2차 다항식으로 근사 시키고 적분값을 구하는 방법이다.
여기서 와 를 각각 와 로 설정했으며 적분 결과는 다음과 같다.
이다.
Simpson 1/3 공식을 단일 구간에 적용하면 다음과 같은 절단 오차를 가지는 것을
증명할 수 있다.
,
여기서 는 구간 와 사이에 존재한다.
결과적으로 Simpson 1/3 공식은 단지 세 점에 근거한 방법이지만 3차의 정확도를 가지는 방법이다.
□ 연구주제의 선정
○ C언어 프로그래밍을 혼자 독학으로 공부하는 친구가 컴퓨터를 이용하여 방정식을 풀고 싶은데 어떻게 해야 할지 모르겠다고 친구들에게 얘기하며 컴퓨터는 우리처럼 인수분해 를 하는지, 아니면 공식을 많이 알고 있는지 궁금하다고 함. 이에 관심을 보이는 학생들이 모여 교사에게 질문을 하였고 교사는 학생들에게 수치해석적인 방법이 있다고 소개함으로서 연구가 시작 됨.
□ 연구 방법
○ Brent’s Method의 풀이법중 역이차법 단계를 Newton’s Method 또는 Secant Method로 변형하여 알고리즘을 구성하고 비교 연구함.
○ Simpson 1/3 방법에서 적분값의 정확도를 효과적으로 높이기 위해 적분구간을 무조건 작게 자르지 않고 적당한 크기로 자른 후 실제 적분값과 수치적분값의 차이가 많이 나는 구간을 더 잘게 나누어 적분의 정확도를 높이를 방법을 탐구함.
□ 연구 활동 및 과정 요약
○ 처음에는 방정식 풀이를 위한 새로운 알고리즘을 개발하려 했으나 아이디어를 내 봐도 기존에 있던 방법과 중복되어 연구방향의 수정이 필요함을 인식하게 됨.
○ 기존의 방정식 풀이법을 탐구하고 그 중에서 효과적인 방법을 선택하여 그 방법을 개선하는 것으로 연구 방향을 조정함.
○ Brent's Method의 과정에 담겨있는 역이차법을 뉴튼법과 할선법으로 대체함. 처음에는 방정식 풀이를 위한 새로운 알고리즘을 개발하려 했으나 아이디어를 내 봐도 기존에 있던 방법과 중복되어 연구방향의 수정이 필요함을 인식하게 됨.
○ 적분법을 개발 할 때는 기존의 방법을 조사하고 그 중에 한 가지 방법을 찾아서 개선하려 고 함. 수치적분 알고리즘은 방정식 풀이 알고리즘 보다 훨씬 복잡하고 어려운 것들이 많아서 이해하기 쉽고 많이 사용되는 Simpson 1/3 방법을 개선하기로 함.
○ GeoGebra를 이용하여 시뮬레이션을 했으며 그 과정에서 알고리즘을 개선할 아이디어 를 탐구함.
○ Simpson 1/3 방법에서 실제 적분값과 수치적분 값의 차이가 많이 나게 되는 조건을 설정하고 새로운 조건을 추가하여 알고리즘을 변경 한 후 다시 시뮬레이션을 하며 아이디어를 검증함.
□ 연구활동 결과
1. 수치 방정식 해법 연구
가. Brent method에서 할선법과 역이차법을 뉴튼법으로 대채하여 근의 수렴여부와 속도를 탐구해 봄.
계산의 편의를 위하여 간단한 방정식 의 근을 찾는 과정을 비교 하고 탐구한다. 이 방정식의 근은 로 자명하지만 연구를 위하여 수치해석적인 방법을 이용하여 근을 구한다. 오차범위
초기 구간을 으로 하면 , 이 되어 이고
을 만족한다.조건1.
와 사이에 가 있어야먄 을 로 채택 조건2. 이전 추정에 이분법이 사용되었다면 부등식
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분법이 사 용된다.
조건3. 이전 추정에 할선법 또는 역이차법이 사용되었다면
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분법이 사 용된다.
조건4. 또한 이전 추정에 이분법이 사용되었다면 부등식
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분법이 사 용된다.
조건5. 이전 추정에 할선법 또는 역이차법이 사용되었다면
을 만족하여야만 다음 추정에 할선법 또는 역이차법이 사용되고 그렇지 않으면 이분법이 사 용된다.
조건6. 이라면 이 보다 더 나은 추정이므로 과 의 값을 서로 맞바꾼다.
나. 변형된 Brent법으로 추정
′ 이고 첫번째 추정을 위하여 ′
을 계산한다.
이고 이는 조건1을 만족하므로 로 선택한다.
두번째 추정에서 이고 이는 조건3에 맞지 않으므로 을
으로 선택한다.
세번째 추정에서 이고 이는 조건1, 조건4, 조건5에 맞지 않으므로
을 으로 선택한다.
네번째 추정에서 이고 위의 조건을 모두 만족하므로 으로 선택한다. 이와 같은 과정을 반복하여 적용하고 할선법과 역이차법을 이용한 Brent method와 비교한다.
다. 추정결과 비교
Brent method
추정 뉴튼법 이용 할선법과 역이차법 이용
1st 1.17284 1.23256
2nd -1.41358 1.14205
3rd -2.70679 -1.42897 4th -3.05510 -2.71449 5th -3.00146 -3.35724 6th -3.00001 -3.03587
7th -2.99436
8th -2.99994
위의 결과를 비교해 보면 뉴튼법을 이용할 때, 더 빠르게 방정식의 근 수렴 함을 확인 할 수 있다.
라. 적용 사례
a. cos tanln
초기구간
, 추정시에 가위치법 사용, 부터 Secant Method 사용
되는 근 찾기 비교
결과: 4번 추정시 원하는 결과를 얻었음. 근은 로 추정함.
b. cos cos
초기구간
, 추정시에 가위치법 사용, 부터 Secant Method 사용
되는 근 찾기 비교
결과: 4번 추정시 원하는 결과를 얻었음. 근은 로 추정함.
2. 수치 적분 해법 연구
가. 기존의 Simpson 1/3 방법의 문제점
- Simpson 1/3방법은 함수의 세 점을 이차함수로 보간하여 적분값을 계산하는 방 식으로 구간 내에서 함수의 변화가 큰 경우 오차가 크게 발생함. 이때, 수치해석 적분 구간을 더 많이 분할하면 적분값은 오차가 줄어들지만 계산 시간이 많이 걸리는 단점 이 있음.
구간[0,1]에서 실제 함수 sin의 적분값이 이고 보간다항식의 적분값은
로서 오차가 크게 발생함.
- 따라서, 구간 내에서 실제 적분값과 수치해석 적분값이 차이가 많이 나는 조건을 찾아 그 구간에서만 구간을 더 분할하여 효과적으로 적분의 값을 정확하게 하는 알고 리즘 개발.
- 구간 에서의 함수의 기울기와 에서의 함수의 기울기의 차이가 1.5배 이 상 차이나는 경우에는 구간을 2배로 분할하여 적분 값을 계산함.
이 경우, 구간을 2배 더 잘게 나누어 보았더니 sin의 실제적분값이 이고 보 간다항식의 적분값은 로서 오차가 줄어듬.
- 이 알고리즘은 각각의 수치해석 적분구간에 적용하여 속도를 많이 떨어뜨리지 않고 수치적분값의 정확도를 높임.
□ 월별 추진 실적
4월: 팀 결성, 연구방향 설정 5월: 수치해석 방정식 풀이법 탐구 6월: 기존의 방정식 풀이법 정리
7월: Brent's Method의 방법적 변화 모색 8월: 여러가지 함수로 새로운 알고리즘시뮬레이션 9월: 수치해석 적분법 탐구
10월: Simpson Method 변형방법 탐구 11월: 새로운 적분 알고리즘 시뮬레이션
*위의 연구와 함께 C언어 프로그래밍 진행
3. 연구 결과 및 시사점
□ 연구 결과
○ 기존의 수치해석 방정식 풀이법 중에서 Brent’s Method의 역이차법을 Secant Method로 변형하여 적용.
○ 기존의 Brent’s Method 보다 빠른 수렴을 확인 함.
○ 기존의 수치해석 적분 풀이법 중에서 Simpson 1/3의 구간을 조건에 따라 더 세밀하게 나누는 알고리즘을 만들어 적용.
□ 시사점
○ 수학시간에 배운 함수의 방정식 풀이와 적분의 풀이가 컴퓨터에서 어떤 방식으로 다르 게 사용되는지 배울 수 있었음.
○ 기존의 수치해석 방법을 수정하고 개선하여 탐구함으로서 수학의 다양한 접근법에 대하여 탐구하고 이해함.
4. 홍보 및 사후 활용
□ 사후 활용 및 과제
○ 이번 연구를 계기로 수치해석 미분법, 최댓값과 최솟값 찾는 법 같은 다양한 분야의 접근을 시도하고 공학에서 사용되는 수학을 간접 경험함.
○ 알고리즘을 C언어로 프로그래밍 하는 과정을 통해 프로그래밍을 실습해보고 알고리즘 의 최적화에 대해 탐구함.
5. 참고문헌
□ 참고문헌
○ Atkinson·Han(2003), Elementray Numerical Analysis
○ Chapra(2009), 공학도를 위한 수치해석 [6판]
○ Steven C. Chapra(2012), 응용수치해석 [3판]
○ Brian W. Kernighan(2016), Kernighan의 C언어 프로그래밍
○ Forouzan(2010), 구조적 프로그래밍을 위한 C언어
