태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          

Notice


안녕하십니까 Mr. K입니다

어제 저녁 내내 친구와 놀고 늦게 들어온 덕분에

포스팅하다가 피로를 이기지 못하고 자고 씁니다 -_-;



시작할게요!



여러분은 다음과 같은 식을 보면 □를 구할 수 있습니까?

[그림 1]


아마 중학교를 졸업한 수준의 학생들이라면 대부분 답을 구할 수 있을 것입니다 ( 답은 1이죠 )

이제 위 그림의 □를 x로 바꿔보겠습니다

[그림 2]


이제 이것을 방정식이라고 부를 수 있을 것입니다
( 사실 그림1, 2 모두 방정식이지만, 그림1과 같은 식을 통해서 배울 때는 방정식이라는 말을 보지 못했을 수도 있으므로 )

미지수 x의 차수가 1이므로 이것은 일차방정식입니다


이런 일차방정식이 두 개 이상 묶여있는 경우엔
그것을 연립일차방정식( 이하 연립방정식이라고 하겠습니다 )라고 합니다 ( 앞의 연립은 '연립주택'의 연립 )

다음 연립방정식에서 x와 y를 구할 수 있습니까?



답은 x = 1, y = 1입니다
첫째줄의 식에서 둘째줄의 식을 빼면 y의 값이 구해지고, 그 y의 값을 둘 중 아무데나 대입하면 x의 값이 구해집니다

푸는 방법이 왜 그런지 이해하지 못할 수 있지만, 어쨌든 답을 쉽게 구할 수 있습니다



그러면,
다음과 같은 연립방정식에서도 미지수 x와 y의 값을 쉽게 구할 수 있을까요?



사실 쉽습니다만 -_-; 복잡하다고 생각해보죠

이런 연립방정식은 다음 그림처럼 행렬의 곱으로 바꿔서 생각할 수 있습니다



그러면 눈에 보이시나요?

AX = B 꼴의 식이므로 양변의 왼쪽에 A의 역행렬( 존재한다면 )을 곱해주기만 하면 미지수의 값을 쉽게 구할 수 있습니다 :D
이 때, 이런 A를 연립방정식의 계수행렬이라고 합니다


한번 해볼까요?

우선, 계수행렬을 {3 4; 8 7}이라 하면 이것의 행렬식은 -11입니다
따라서 역행렬이 존재하겠지요

그러면 다음과 같은 과정을 거쳐서 x와 y를 구할 수 있습니다 :)




그런데, 과연 이 방법을 모든 연립방정식에 적용할 수 있을 것인가? 하면
그것도 아닙니다

역행렬이 존재하지 않는 녀석들이 있기 때문에
그런 계수행렬과 대응되는 연립방정식은 다른 방법으로 해결을 해야 합니다


아래의 두 케이스를 보시면,

[그림 7]

[그림 8]


두 케이스 모두 계수행렬의 역행렬을 구할 수 없습니다

이 때, 역행렬을 구할 수 없다는 것은
연립방정식의 첫째줄의 식의 양변에 적당한 수를 곱하면 둘째줄의 식의 좌변( 미지수 )을 0으로 만들 수 있음을 의미합니다
( 이것은 나중에 미지수의 개수가 많아지면 조금 더 엄밀하게 정의가 되겠지만, 지금은 기초적인 것을 얘기하고 있으므로 패스합니다 )


무슨 말이냐면,

그림 7의 연립방정식은 첫번째 줄에 17을 곱해서 두번째 줄을 빼버리면 다음과 같이 됩니다



마찬가지로, 그림 8의 연립방정식은 첫번째 줄에 17을 곱해서 두번째 줄을 빼버리면 다음과 같이 됩니다



모순이 등장했지요?
이렇게 판정하면 됩니다

계수행렬의 역행렬이 존재하지 않는 케이스의 경우,
( 미지수가 2개일 때는 ) 한 줄의 식이 다른 줄의 식의 배수가 되므로 위에서 한것처럼 빼보면

빼진 줄의 식이 0 = 0이 되거나 0 = k이 됩니다 ( k는 0이 아닌 실수 )

0 = 0이 되면 주어진 연립방정식을 참이 되게 하는 x, y의 개수는 무한하고,
0 = k가 되면 주어진 연립방정식을 참이 되게 하는 x, y는 없습니다



미지수가 3개 이상일 때도 계수행렬을 이용해서 푸는 방법이 많이 쓰이는데,
그것은 여기서 언급하지 않고 넘어가기로 하겠습니다



여기까지가 행렬의 기본입니다

심화된 부분을 더 포스팅할지 말지는 생각해보고 결정하도록 하겠습니다 =_=


(포스팅 소요시간 : 약 75분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 5  (0) 2009.03.14
Matrix : Part 4  (0) 2009.03.06
[Bigfloat 지원사격?] 자연수부터 해봅시다 :)  (4) 2009.02.26
Matrix : Part 3  (0) 2009.02.09
Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
posted by Milkskin

댓글을 달아 주세요


안녕하십니까 Mr. K입니다

여기에 글을 쓰는것도 오랜만이군요 -_-;

원래 어제 올렸어야 되는데
수정된 ubint를 올려놓고 딴짓좀 하다보니 잊어버렸지 뭡니까;

그래서
공지를 띄우고 며칠 더 있다 올릴까, 지금 올릴까
하다가 지금 올립니다 -_-;



이번 포스트는 역행렬에 대해서 얘기해보겠습니다



이전까지 우리는
행렬의 기본적인 정의, 행렬간 덧셈·뺄셈의 정의, 행렬간 곱셈의 정의
등을 배웠습니다

행렬은 나눗셈의 개념은 없지만, 역행렬이라는 것이 있습니다


실수를 다룰 때, 다음과 같은 관계에서 a가 0이 아니라면 x, 즉 a의 역수를 생각해볼 수 있습니다


마찬가지로 행렬에서도,
다음과 같은 관계를 만족하는 행렬 A에 대해서는 X, 즉 A의 역행렬을 생각해볼 수 있습니다

[그림 2] A와 X 사이에 교환법칙이 성립해야하므로
A와 X는 모두 정사각행렬이다

그리고
A가 어떤 조건을 만족하여 역행렬이 존재함을 알게 된다면, 우리는 그 역행렬을 다음과 같이 표기합니다

[그림 3] 읽을 때는 A inverse라고 읽으면 됩니다
다른 행렬 B가 있을 때 그 역행렬이 존재한다면, B의 역행렬은 B inverse라고 읽으면 됩니다


그럼 이제, 간단한 예제를 가지고 역행렬을 직접 구해보도록 하겠습니다


어떤 행렬이 역행렬을 가지게 될 조건은 잠시 후에 언급하기로 하고, A의 역행렬을 구해봅시다

이 경우 역행렬이 존재하므로, ( 일부러 존재하는 case를 선택함 )
그림 2( AX = XA = E )의 관계를 만족하는 행렬 X를 구해보면 됩니다

그래서 A의 역행렬을 다음과 같이 놓으면, 그림의 두번째 줄에 있는 식이 성립합니다

[그림 5]

그럼 먼저,
A를 왼쪽에, A의 역행렬을 오른쪽에 곱한 것을 계산해보면 다음과 같습니다


마찬가지로
A의 역행렬을 왼쪽에, A를 오른쪽에 곱한 것을 계산해보면 다음과 같습니다


이렇게 구한 A의 역행렬은 그림 5의 두번째 줄에 있는 식을 만족합니다 ( 검산은 직접 :D )



하지만 행렬도 역행렬이 존재하지 않는 놈들이 있습니다, 마치 0의 역수가 존재하지 않는 것처럼

다음과 같은 행렬은 역행렬이 존재하지 않지요




그럼 이쯤에서 역행렬을 가지게 될 조건에 대해 봅시다

원래는 A의 원소를 임의로 정해놓고 역행렬을 구하는 과정을 보여드리면서 조건에 대해 얘기해야 하지만,
귀찮으니까 공식을 통해 보도록 하겠습니다 -_-;


네, 위 그림의 두번째 줄을 천천히 읽어보시면 조건이 나와있습니다
A의 원소를 1행 1열부터 각각 a, b, c, d라고 했을 때, ad-bc가 0이면 되는거죠

이 때, ad-bc를 행렬식( determinant )이라고 하고 줄여서 D로 쓰곤 합니다
( 대학에 가서 선형대수학을 배우게 되면 D는 행렬식 대신 다른 의미를 갖게 되는데, 여기서는 일단 패스 )

그럼 이제 아까의 문제를 되돌아봅시다

조건같은 것을 생각하지 않고 다짜고짜 역행렬을 구했던 녀석은 D를 계산해보면 1×1 - 0×2 = 1이 나옵니다
그러면 공식에 의해서 역행렬을 구할 수 있지요, 물론 직접 계산해도 됩니다 :)

그리고 조건을 언급하기 직전에
역행렬이 존재하지 않는다고 했던 녀석은 D를 계산해보면 1×4 - 2×2 = 0이 나옵니다
그래서 이녀석은 역행렬을 구할 수 없습니다


다음 포스트에서는 행렬을 가지고 연립방정식을 푸는 것에 대해 언급할 것인데,
이처럼 역행렬이 없는 녀석들은 연립방정식의 해가 없거나 무한히 있거나 둘 중 하나가 되곤 하지요

뭐 어쨌든, 이제 역행렬의 성질에 대해 알아보겠습니다



첫째로, 역행렬의 역행렬은 자기 자신이 됩니다


위 그림을 보시면 A의 역행렬은 A inverse지만, 반대로 생각하면 A inverse의 역행렬이 A이기도 합니다

[그림 11] 마치 음수의 음수가 양수이듯이,
혹은 역수의 역수가 자신이듯이


둘째로,
각각 역행렬이 존재하는 두 행렬 A, B의 곱의 역행렬은 존재하고, 그것은 각각의 역행렬을 역순으로 곱해놓은 것과 같습니다

[그림 12] ∃는 exist라는 의미의 기호, 아마 고등학교 과정에서는 볼 일이 없을 것

다만, A와 B의 곱이 존재하기 위해서는 A와 B가 같은 꼴의 행렬이어야 한다는 것은 말하지 않아도 되겠지요?

[그림 13] AB와 그것의 역행렬로 추정되는 것과의 곱
곱의 결과가 단위행렬이 되므로 역행렬이 맞다
마찬가지로, BA의 역행렬이 존재한다면 (BA inverse) = (A inverse)×(B inverse)


마지막으로, 지수에 관한 성질도 한가지 있는데
A가 역행렬이 존재한다면, A의 거듭제곱의 역행렬A의 역행렬의 거듭제곱과 같습니다

[그림 14] 두번째 줄의 식은 k가 1일 때는 당연하다


이제, 역행렬에 관한 예제 하나를 풀어보고 이번 포스트를 마치도록 하겠습니다


위의 식을 만족하는 X를 구하면 됩니다

X의 왼쪽에 곱해진 행렬을 A라 하면, A의 행렬식은 0이 아니므로 역행렬을 구할 수 있습니다

그래서 양변의 왼쪽에* A의 역행렬을 곱해줍니다


*양변의 왼쪽에 : 행렬은 일반적으로 교환법칙이 성립하지 않으므로 왼쪽에 곱하는 것과 오른쪽에 곱하는 것의 결과가 각각 다른데, 위에서는 X와 A 사이에 교환법칙이 성립하는지의 여부를 알 수 없으므로 A의 역행렬을 오른쪽에 곱하게 되면 문제만 복잡해진다


그리고 다음과 같이 계산하면 됩니다


참 쉽죠? :D





이번 포스트는 여기까지입니다

다음번에는 연립일차방정식과 행렬에 관해 얘기하겠습니다 (__)


(포스팅 소요시간 : 약 90분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 5  (0) 2009.03.14
Matrix : Part 4  (0) 2009.03.06
[Bigfloat 지원사격?] 자연수부터 해봅시다 :)  (4) 2009.02.26
Matrix : Part 3  (0) 2009.02.09
Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
posted by Milkskin

댓글을 달아 주세요


※ 발행할까 말까 고민좀 했는데, 내 정기 포스트가 아니라 일단 발행에 체크 안함 - to 관리자


안녕하십니까 Mr. K입니다


원래 오늘 제 포스트( 행렬 )를 끄적이기로 했던 날입니다만

환타님이 Bigfloat 만드신 것을 보고서 왠지 불타올라서(?)

개인적인 의견도 끄적이고 구현까지 해버렸습니다 -_-;


일단 저는 Talk에 끄적여놓았듯이

Bigfloat을 만들기 위한 기반은 Bigint라는 생각이 들고, Bigint를 만들기 위한 기반은 Unsigned Bigint라는 생각이 들어서


자연수의 역할을 하게 될 Unsigned Big INTeger를 먼저 만들어보았습니다

클래스의 정의부분입니다


자연수의 역할을 하기 때문에 부호를 나타내는 부분은 없고,
숫자열의 역할을 하는 부분은 string을 사용하였습니다

환타님이 포스트에 걸어놓은 링크를 타고 가면 나오는 모 중국인( 이라 추정 )이
Bigint를 구현할 때 string을 사용해놓은 것이 상당히 편리한 것 같아서 그것을 따왔습니다

자연수는 덧셈과 곱셈에 대해서만 닫혀있기 때문에 구현도 덧셈과 곱셈에 대해서만 해놓았습니다

add함수와 multiply함수는 ubint의 기능을 상속받는 bint( Big INTeger )에서 사용하기 위해
input과 output을 string으로 설정하였습니다

그 아래로는 죄다 연산자 오버로딩이므로 패스-



클래스의 구현부분입니다 ( 주의: 스압-_-이 조금 )


길어서 따로 설명은 하지 않겠습니다 -_-;

string함수와 substr함수를 이용하는 것도 위에 언급한 중국인이 사용해놓았습니다만, 따왔습니다

혹시 저작권이나 기타 다른 문제가 발생하지 않을까 조금 걱정이 되긴 합니다만
핵심이 되는 add함수와 multiply함수의 알고리즘은 직접 만든 것이므로 내껍니다 (?)

그리고, 연산자 오버로딩을 할 때
ubint에 음수가 존재하지 않으므로, 피연산되는 int형에 음수가 나오면 절대값을 취해버렸습니다

나머지는 패스-



main함수에서 실행해보았습니다
( 실제 제 workspace에는 더 많이 테스트되어있지만 정리가 안되어있는 관계로 하나만 -_-; )





아주 잘 나오네요 :D





이 포스트는 여기까지입니다/

어제 개인적인 의견을 끄적이고나서부터 만들기 시작해서

오늘 자잘한 버그까지 잡느라 간만에 머리좀 굴렸네요 ㅋㅋ


정기 포스트 대신이라고 봐주시면 감사하겠습니다

싫으셔도 할 수 없어요 :D


혹시나 댓글로 요청이 들어오거나 하면 이것을 기반으로 조금 더 만들어볼 의향은 있습니다만,
왠지 환타님 것을 가로채는게 아닌가 싶어 좀 걱정이 되긴 합니다 =_=


(포스팅 소요시간 : 약 45분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 5  (0) 2009.03.14
Matrix : Part 4  (0) 2009.03.06
[Bigfloat 지원사격?] 자연수부터 해봅시다 :)  (4) 2009.02.26
Matrix : Part 3  (0) 2009.02.09
Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
posted by Milkskin

댓글을 달아 주세요

  1. 가로채셔도 괜찮습니다 ㅋㅋ

  2. 고래도 팀프로젝트인듸 ㅁ_ㅁ 나도 코드 좀 깔짝거려야 하남;

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.02.28 04:46  Addr Edit/Del

      ㅇㅇ 그러든지 ㅋㅋ

      난 지금 bint 손코딩 절반정도 끝난듯 =_=


안녕하십니까 Mr. K입니다

지난 포스트에서도 언급했듯이 사정이 좀 생겨서

군대 안가고 약 1년정도 휴학할 예정이나, 그동안 돈을 벌어야 하는 관계로
Matrix의 포스팅이 끝나면 한동안 주간포스트를 접어야 할수도 있겠습니다



오늘 다룰 내용은 행렬의 연산, 그중에서도 곱셈에 대해 다루고자 합니다

영희의 어머니는 할머니의 생신을 맞아 송편과 인절미를 만들려고 한다. 송편과 인절미를 각각 1000g씩 만드는 데 필요한 재료의 양과 각 재료의 1g당 가격은 다음 표와 같다. 아래의 물음에 …



위의 글상자에서 송편과 인절미를 만드는 데 필요한 비용을 구하는 식은

송편 : 650×2 + 300×3 + 50×1 = 2250 (원)
인절미 : 780×2 + 200×3 + 20×1 = 2180 (원)

임을 알아보았습니다


이 때, 송편과 인절미를 만드는 데 필요한 재료의 무게를 행렬 A로,

송편과 인절미를 만드는 데 필요한 재료의 1g당 가격을 행렬 B로 나타내고,

송편과 인절미를 만드는 데 필요한 비용을 행렬 C로 나타내면

세 행렬 A, B, C 사이에는 다음과 같은 관계가 있음을 알 수 있습니다



일반적으로 m×n행렬 A와 n×p행렬 B에 대하여, 행렬 A의 i번째 행의 각 성분과 행렬 B의 j번째 열의 각 성분을 그 순서대로 곱하여 더한 것을 (i, j)성분으로 갖는 행렬을 두 행렬 A와 B의 곱이라고 하고, 기호로는 A × B, AB로 나타냅니다

일단 이 Matrix 포스트에서는 2×2행렬을 주로 다룰 것이므로 2×2행렬의 곱에 대해 보게 되면 다음과 같습니다

두 행렬은 같은 꼴이 아니어도 상관없으나,
'왼쪽행렬의 열의 수'와 '오른쪽행렬의 행의 수'는 같아야한다

그렇기 때문에
A가 m×n행렬이고 B가 p×q행렬이라면,

n = p일때만 곱 AB가 정의되고, AB는 m×q행렬이 됩니다
( 반대로 BA를 생각하면, q = m일때만 곱 BA가 정의되고, BA는 p×n행렬이 됩니다 )



행렬의 곱은 위에서 보신 것처럼 약간 특이하게 정의되기 때문에, 일반적으로 교환법칙은 성립하지 않습니다

그러나 결합법칙, 분배법칙 등은 수를 다룰때와 마찬가지로 성립하지요

위의 것이 결합법칙, 중간의 두줄이 분배법칙, 아래의 것은 상수배에 관한 것이다 (k는 실수)
행렬은 일반적으로 교환법칙이 성립하지 않기 때문에
분배법칙의 경우 왼쪽에 곱한 것과 오른쪽에 곱한 것을 따로 설명한다

수를 다룰 때, 같은 수를 여러번 곱한 것을 거듭제곱으로 나타내는데,
행렬에서도 이와 같은 표현을 사용합니다
즉,



아, 증명없이 말만 하고 넘어갈 것이 하나 있습니다
수에서는 0이 아닌 두 수를 곱하게 될 경우 그 결과 역시 0이 아니지만,
행렬에서는 영행렬이 아닌 두 행렬을 곱해도 결과가 영행렬이 되는 경우가 있습니다



정사각행렬중에

처럼 대각성분*은 1이고 나머지는 전부 0인 정사각행렬을 단위행렬( identity matrix )이라고 합니다
흔히 I( 대문자 i ) 또는 E로 나타내는데, 여기서는 E로 쓰겠습니다


*대각성분 : (1, 1)성분, (2, 2)성분, (3, 3)성분, …과 같은 것들
이것들을 모아놓으면 행렬의 대각선이 되며, 현재 필자는 정사각행렬에 대해서만 '대각' 얘기를 할 수 있다고 알고 있음


이것도 증명없이 말만 하고 넘어갈 것입니다만
단위행렬은 임의의 행렬과 곱하게 될 경우 교환법칙이 성립합니다
즉, 다음과 같습니다
'수의 곱셈'에서의 '1' 과 같다고 생각하면 된다


오늘은 여기까지 쓰겠습니다
다음 포스트에서는 역행렬에 대해 다룰 것입니다

간만에 포스팅하니 별로 하는 것 같지도 않고 그러네요 -_-a 중간에 딴짓도 많이하고


(포스팅 소요시간 : 약 110분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 4  (0) 2009.03.06
[Bigfloat 지원사격?] 자연수부터 해봅시다 :)  (4) 2009.02.26
Matrix : Part 3  (0) 2009.02.09
Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
Matrix Decomposition  (1) 2009.01.08
posted by Milkskin

댓글을 달아 주세요


안녕하세요 Mr. K입니다

사정이 좀 생겨서 아마 matrix의 포스팅이 끝나고나면 한동안 주간 포스트를 접어야 할지도 모르겠습니다;
(하지만 문제는 시간 나는대로 풀어서 올릴 예정)


오늘 다룰 내용은 행렬의 연산입니다

다음 표는 영희네 옷가게에서 어제까지 보유한 물량과 오늘 구입한 물량을 나타낸 것이다. 이 표를 보고 …




위의 글상자에서 어제까지 영희네 옷가게에서 보유한 물량과 오늘 구입한 물량을 각각 아래와 같이 행렬로 나타내기로 합니다


그러면 영희네 옷가게에서 현재 보유하고 있는 각 옷의 물량은 아래 표와 같습니다


이 때, 이 표의 성분은 A와 B의 대응하는 성분의 합이고, 이것을 행렬로 나타내면 다음과 같습니다


이처럼 행렬 A와 행렬 B의 대응하는 성분의 합을 성분으로 갖는 행렬을 A + B로 나타내고 A와 B의 합이라고 합니다
앞의 행렬 A, B에 대해서 A+B를 구하면 아래와 같습니다



일반적으로, 같은 꼴의 두 행렬의 덧셈은 다음과 같이 대응하는 성분의 합으로 정합니다

두 행렬이 같은 꼴이 아니라면 덧셈은 정의되지 않습니다

그러면 행렬의 덧셈은 수를 다룰 때와 마찬가지로 다음과 같은 교환법칙이나 결합법칙이 성립합니다
(증명은 관심있는 사람들만 직접 해보세요 :D)

위의 것이 교환법칙, 아래의 것이 결합법칙
아래와 같은 연산의 경우 괄호를 생략하기도

추가로, 성분이 모두 0인 행렬을 영행렬( zero matrix )이라고 합니다
예를 들면, 다음의 그림은 각각 1×2행렬, 2×1행렬, 2×2행렬, 2×3행렬인 영행렬입니다


영행렬은 행과 열의 크기에 관계없이 보통 대문자 o를 사용해서 나타냅니다
(관계가 없다기보다는, 보통 영행렬이 아닌 다른 행렬의 크기에 맞춰서 생각하곤 합니다)

그러면 이 영행렬은 임의의 행렬 A에 대해 다음을 만족합니다




덧셈이 있다면 뺄셈도 있어야겠지요?

아래와 같은 세 행렬에 대해


A + B = O가 성립한다면, B의 성분은 무엇이 되어야 할까요?

우리는 위에서 행렬의 덧셈을 다루었기 때문에, 그 과정은 자연스럽게 다음과 같이 이루어집니다


그리고
이전 포스트에서 행렬이 같을 조건에 대해 알았고,
수에 대한 사칙연산은 이미 알고 있으니 다음과 같은 과정이 이루어집니다


그러면 행렬 B의 각 성분은 행렬 A의 각 성분의 부호를 바꾼 것과 같아집니다


이제 임의의 행렬 A에 대해서,
A의 각 성분의 부호를 바꾼 것을 성분으로 갖는 행렬을 -A로 나타내기로 합니다

그러면, 임의의 행렬 A에 대해서 아래의 그림이 성립합니다



이제 같은 꼴의 A, B에 대하여 A + (-B)를 A - B로 나타내고, 이것을 A에서 B를 뺀 차라고 합니다

두 행렬이 같은 꼴이 아니라면 뺄셈도 정의되지 않습니다



다음은 행렬의 실수배에 대해서 보겠습니다

어느 도시의 현재 대중 교통 요금은 다음 표와 같다고 한다.


앞으로 10년 뒤에 이 도시의 대중 교통 요금은 현재 요금의 두 배가 된다고 할 때, 다음 물음에 …

위의 글상자에 나온 표를 행렬로 쓰면 아래와 같습니다


그리고 10년 후의 요금은 각각 현재 요금의 두배이므로 이것을 행렬로 나타내면 아래와 같습니다



이제 M'과 M을 비교해보면
M'의 각 성분은 M의 각 성분을 2배한 것과 같음을 알 수 있습니다


이 때, 행렬 M'을 간단히 2M으로 나타내기로 합니다


일반적으로, 임의의 행렬 A의 각 성분에 임의의 실수 k를 곱한 것을 성분으로 갖는 행렬을
행렬 A의 k배라고 하고, 이것을 기호로 kA라 나타냅니다

여기서 R은 실수집합을 뜻한다


그러면 1A = A, (-1)A = -A, 0A = O, kO = O 가 자연스럽게 성립하게 되겠지요


행렬의 실수배에 대해서는 다음과 같은 법칙이 성립합니다

A, B는 같은 꼴의 행렬이고,
m, n은 임의의 실수이다



이번 포스트는 여기까지 쓰는 것으로 하겠습니다

행렬의 곱셈까지 설명하려고 했지만, 지금 이것도 (그림덕분에) 나름 스압이 쩔어서요 -_-;
아마 역행렬까지 언급할 수 있지 않을까 싶네요

(포스팅 소요시간 : 약 90분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

[Bigfloat 지원사격?] 자연수부터 해봅시다 :)  (4) 2009.02.26
Matrix : Part 3  (0) 2009.02.09
Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
Matrix Decomposition  (1) 2009.01.08
무리수 √2의 값을 구해보자! : Part 5  (3) 2008.12.27
posted by Milkskin

댓글을 달아 주세요

  1. 군대도 좀 늦게 간대매 -ㅁ-


안녕하십니까 Mr. K입니다

어제 그제 노느라 제대로 포스팅을 못했습니다 -_-;

오늘도
간이 나빠져서 입원하신 부친 병문안 다녀오는 일이 있어서 그냥 다음주로 미룰까 하다가

하루종일 병원에 있는 것도 아니고 해서 늦게나마 포스팅합니다/



지난번 포스트에도 Matrix에 대한 내용을 적어놓고 왜 또 이번에 Matrix를 다루는지 의아해 하실 분들이 있겠습니다만 (있나?)

이 팀블로그에서 하는 일이 주간 포스트만 있는 것이 아니지요,
바로
알고리즘 대회 기출문제.. 라고 생각되는 것들을 임의로 골라서 같이 풀어보고 토론(..)하는 일도 하고 있습니다만

번역되는 문제들을 보면 (혹은 개인적으로 문제 리스트를 훑어볼 때에도)

종종 문제 자체에서 Matrix를 이용하거나
Matrix를 이용해서 풀면 쉬울듯한,

그것도 아니라면 최소한 Matrix를 이용해서 알고리즘을 세우는 것 정도는 가능하게 되어있는 문제들이 있었습니다

다른 멤버들이야 다들 고졸 학력을 가지고 있으니까 그닥 상관없겠지만
환타님은 이제 곧 중졸 학력을 갖게 되지요 (아직 졸업식을 안했으니 현재는 초졸이라고 불러야 할수도 -_-;;)

그렇다보니, 예습을 하지 않았다면
Matrix, 즉 행렬에 관한 지식이 전무한 상태라

나머지 고졸 멤버들이 행렬을 이용해서 쉽게 알고리즘을 설계하는 동안
조금 더 머리를 싸매고 고민해야한다는 문제가 발생합니다



그래서 이번 포스트부터 한동안은 행렬의 기초부터 천천히 포스팅 할 생각입니다

시작할게요!



컴퓨터를 만드는 어느 회사는 두 공장에서 컴퓨터를 생산하고, 이것을 세 곳의 대리점으로 보낸 다음 판매한다고 한다. 이 때, 컴퓨터 한 대를 각 공장에서 각 대리점으로 운송하는 비용은 아래 표와 같다. 이 표를 보고 …



위의 글상자에서 운송 비용을 나타낸 표는 아래와 같이 숫자만을 묶어 나타낼 수 있습니다


이처럼 수를 직사각형 모양으로 배열하여 나타낸 것을 행렬( matrix )이라고 하고,
행렬을 이루는 각 수를 그 행렬의 성분( element )이라고 합니다.

행렬에서 성분의 가로배열을 ( row )이라고 하고, 위에서부터 차례로 제 1행, 제 2행, … 이라고 합니다
또, 성분의 세로배열을 ( column )이라고 하고, 왼쪽에서부터 차례로 제 1열, 제 2열, … 이라고 합니다


행의 수가 m, 열의 수가 n인 행렬을 m행 n열의 행렬 또는 m×n 행렬( m by n matrix )이라고 하고,
특별히 행의 수와 열의 수가 같은 행렬을 정사각행렬( square matrix )이라고 합니다

따라서 위 행렬은 2×3 행렬이고,
제 1행과 제 1열은 각각 아래의 그림과 같습니다

제 1행

제 1열

제 i행( i번째 행 )과 제 j열( j번째 열 )이 만나는 위치에 있는 성분을 (i, j)성분이라고 합니다
예를 들면, 위 행렬에서 (1, 2)성분은 2, (2, 1)성분은 2, (2, 3)성분은 3입니다


행렬은 흔히 아래와 같이 대문자를 사용해서 나타내곤 합니다


여기에 하나 덧붙이자면
환타님이 이 내용에 대해 모를것이다 가정하고 시작하긴 했지만, 아마 C를 공부했기 때문에 아실겁니다

바로 위의 그림과 아래의 코드가 같은 내용이라는 것을 -_-;



참고로, 직사각형 모양으로 배열된 자료는 여러가지 모양의 행렬로 나타낼 수 있습니다
아래의 표를 두 행렬 M, N으로 나타낸다고 하면 다음과 같은데,



이 때, 행렬 M의 1행은 영희의 국어, 수학, 영어 성적을 나타내고,
행렬 N의 1행은 영희와 철수의 국어 성적을 나타내게 됩니다



두 행렬 A와 B 각각의 행의 수, 열의 수가 같으면 두 행렬은 서로 같은 꼴의 행렬이라고 합니다

특별히, 두 행렬 A와 B가 서로 같을 꼴이면서 대응되는 성분이 각각 같을 때, 이 두 행렬은 서로 같다고 하고,
기호로는 A = B 로 나타냅니다




이번 포스트는 여기까지 쓰는 것으로 하고,
다음주에 행렬의 연산에 대해 쓰도록 하겠습니다
여유가 된다면 역행렬까지 언급할지도 모르겠네요

(포스팅 소요시간 : 약 85분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 3  (0) 2009.02.09
Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
Matrix Decomposition  (1) 2009.01.08
무리수 √2의 값을 구해보자! : Part 5  (3) 2008.12.27
Interpolation : Part 3  (12) 2008.12.05
posted by Milkskin

댓글을 달아 주세요

  1. 오오 처음으로 Mr.K의 포스트를 한번 읽고 바로 이해했어

  2. 오오 처음으로 포스트중에 이해하는게 생겼어

  3. 그나저나 저는 7지망에 붙었다죠.
    어떻게 다닐지 막막해요 ㅜㅜ
    7지망 붙을 확률이?

  4. 높은 편이에요 제 주변엔 16~17 지망들도 .. (그거랑 그거랑 같을리가 없지만..)

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.01.19 01:40  Addr Edit/Del

      나 다니던 중학교에서는 25개 학교중에 25지망 걸린놈이 딱 하나 있었더랬지 -_-;

  5. 25지망까지 있는 곳도 있나요? ㄷㄷ
    여긴 7지망이 마지막이죠 ㅎㅎ
    가까운 순서대로 했는데 OTL

    • Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.01.19 17:00  Addr Edit/Del

      다른 곳은 모르겠는데, 인천 쪽은 25지망까지 있습니다. -_-;

      멀리 갈 것도 없이 당장 제 동생이 24지망에 걸렸었다죠. -_-...
      25지망에는 1지망 100% 마감일 고등학교 써 넣었었으니, 사실상 마지막이라 봐야합니다. ㄱ-


안녕하십니까 Mr. K입니다

어쩌다보니 처음같지 않게 포스팅이 뜸해지는군요 -_-;

본 내용은 PKU 3685 : Matrix 와는 전혀 관계없는 내용이므로 해당 내용을 보시고자 하는 분들은 뒤로가기를 눌러주세요



오늘 소개할 내용은 행렬 분해법입니다

그 중에서도 LU-분해법(LU-Decomposition)에 대해서 소개하도록 하겠습니다



예전에 소개했던 Interpolation : part 1 에서

N차 다항식을 구하기 위해 N+1개의 점들을 행렬의 원소로 갖는 Vandermonde matrix를 사용했었습니다

그래서 아래와 같은 꼴의 문제로 바뀌게 되었지요


그러나 당시 포스트에도 언급했듯이,

구하고자 하는 다항식의 차수가 커지면 그만큼 오래걸린다는 단점이 존재했습니다



이번에 소개할 LU-분해법은 그 시간을 조금 줄여줄 수 있는 방법입니다

위의 문제를 아래와 같은 꼴로 바꾸어서 푸는 것이지요


이때, L과 U는 각각 다음과 같은 하-삼각행렬(Lower triangular matrix)과 상-삼각행렬(Upper triangular matrix)입니다

*는 임의의 수를 뜻합니다
0이 있어도 상관없습니다

이렇게 분해하면 무슨 장점이 있느냐,
-라고 생각하시는 분들도 있겠지만

A가 희소행렬(sparse matrix)이 아니라면
오히려 이 방법이 가우스-조르단의 소거법보다도 빠른 시간에 문제해결이 됩니다

얼마나 빠른가 하면,

사실 AN INTRODUCTION TO Programming and Numerical Methods in MATLAB에 나온 그래프는
이것보다 더 깔끔한 곡선을 그리고 있고, 두 방법간의 시간차도 더 크게 나와있지만
그대로 그려내기가 쉽지 않더군요 -_-; 이게 그나마 제일 비슷하게(모양만) 나온 그래프인듯 합니다


이정도의 차이를 나타내지요

위의 Full inversion이 가우스-조르단의 소거법이라 보시면 됩니다



이제 그 방법을 보기로 하지요

예시는 Interpolation : part 1 에서 사용했던 Vandermonde matrix를 사용하도록 하겠습니다

1. 먼저, L은 항등행렬로, U는 영행렬로 설정해둡니다



2. U의 1행에 A의 1행을 그대로 복사합니다



3. L의 1열에 A의 1행을 그대로 복사하되,
L의 1행 1열 원소가 1을 유지하도록 (A의 1행 ÷ U의 1행 1열 원소)의 값을 L의 1열에 복사합니다
(여기서는 U의 1행 1열 원소, 즉 A의 1행 1열 원소가 1이기 때문에 나누는 작업이 필요하지 않습니다)
(이 작업을 하기 위해 필요한 조건 : A의 1행 1열 원소는 0이 아니어야 합니다)



4. U의 2행의 원소들을 구합니다
U의 2행 1열은 0으로 놔두고, (∵ U는 상-삼각행렬이므로)
U의 2행 2열은,
위 그림에 나와있는 L의 2행과 U의 2열을 곱해서 나온 수 k를 A의 2행 2열에서 뺀 뒤, L의 2행 2열의 값으로 나누어줍니다
(여기서 k = 1×1 + 1×0 + 0×0 = 1이고, A의 2행 2열은 2, L의 2행 2열은 1이므로 (2-k)/1 = 1을 U의 2행 2열에 대입합니다)
U의 2행 3열도 마찬가지로 구해줍니다



5. L의 2열의 원소들을 구합니다
L의 1행 2열은 0으로 놔두고, (∵ L은 하-삼각행렬이므로)
L의 2행 2열은 1로 놔두고, (∵ L의 대각선은 전부 1로 고정되어있습니다)
L의 3행 2열은,
위 그림에 나와있는 L의 3행과 U의 2열을 곱해서 나온 수 m을 A의 3행 2열에서 뺀 뒤, U의 2행 2열의 값으로 나누어줍니다
(여기서 m = 1×1 + 0×1 + 1×0 = 1이고, A의 3행 2열은 3, U의 2행 2열은 1이므로 (3-m)/1 = 2를 L의 3행 2열에 대입합니다)
(주의사항 : U의 2행 2열의 값이 0일 경우, (3-m)/0을 계산하지 않고 (3-m)만을 계산해서 대입합니다)



6. U의 n행, L의 n열의 원소들을 채우는 작업이 끝날 때까지 4. 와 5. 를 반복합니다


이제 A가 L과 U로 분해되었으니, 조금 더 간단하게 연립방정식을 풀 수 있습니다



코드로 구현한 것은 다음과 같습니다






전에 연분수에 대해 보강한다 어쩐다 했는데

빈둥빈둥 놀다보니 그럴 시간이 안나는군요 -_-; 빨리 분석을 시작해야할텐데;

다음주에는 뭘 소개할지 모르겠지만,

소재를 못찾으면 수학1에 나오는 행렬의 기본 에 대해 끄적일지도.. -_-;


(포스팅 소요시간 : 약 75분)


+α (9:37부터 수정 시작)
포스팅을 끝내고 화장실에서 생각을 좀 해봤는데, A를 LU로 분해했을 때의 장점을 하나 빼먹었군요 -_-;


또 하나의 장점이라면 장점인데,

분해하기 전의 행렬보다 분해하고 난 후의 두 삼각행렬에서 행렬식(Determinant)을 구하는 것이 훨씬 쉽지요
(∵ 삼각행렬의 행렬식은 모든 대각원소의 곱이기 때문에)

그래서 두 삼각행렬의 행렬식을 구해서 곱하면, 그것이 기존 행렬의 행렬식이 되고,
그 값이 0이냐 아니냐에 따라 연립방정식의 해의 존재유무를 더 빨리 알아낼 수 있게 될겁니다


또 하나 빼먹은 것은,
A의 1행 1열의 원소가 0일 경우의 분해방법입니다

다음과 같은 행렬 A에 대해서는 위의 분해방법을 적용할 수 없습니다


그러나 이러한 경우,
행을 치환해주는 행렬 P나 열을 치환해주는 행렬 Q를 이용해서

P는 항등행렬에서 1행과 2행을 치환한 것이고,
Q는 항등행렬에서 1열과 2열을 치환한 것입니다

PA 또는 AQ를 생각하면 이 분해법을 적용할 수 있습니다


(포스트 수정시간 : 약 20분)


+2α (9일 pm 11:03부터 수정 시작)
"플러스 알파" 적을 때 같이 적을려고 했다가 깜빡하고 넘어간게 하나 있네요 -_-;

저 위에 적어놓은 분해방법은
제가 3×3 행렬 몇개를 분해해보고, 그 방법을 일반화한 것입니다


실제로 LU분해법이 소개된 책에, 만약 그 분해법까지 자세히 나와있다면
이 포스트에서 보는 방법과 전혀 다를 수 있으니 참고바랍니다 (_ _)

(포스트 수정시간 : 약 4분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
Matrix Decomposition  (1) 2009.01.08
무리수 √2의 값을 구해보자! : Part 5  (3) 2008.12.27
Interpolation : Part 3  (12) 2008.12.05
Interpolation : Part 2  (0) 2008.11.28
posted by Milkskin

댓글을 달아 주세요

  1. BlogIcon ssu 2014.04.23 15:14  Addr Edit/Del Reply

    감사합니다


안녕하십니까 Mr. K입니다

오랜만의 포스팅이군요 -_-;


지난주에 예고했던 것 처럼 √2에 대한 얘기를 하나 끄적이도록 하겠습니다

아, 그 전에
이번 포스트의 경우 도함수에 대한 얘기가 있으니, √2를 구하는 방법을 하나만 알아도 된다 하시는 분들은 패스하셔도 됩니다

Fixed Point Iteration
Most of the techniques we will discuss are iterative in nature and the first one is called the fixed point iteration scheme. Instead of looking for a zero of the function f(x), it determines a fixed point of an equivalent equation. The equation is rewritten in the form x = g(x), so when x is substituted in the function g(x) it returns the value x, hence the nomenclature fixed point. The converstion of the equation f(x) = 0 into one of the form x = g(x) is not always straightforward and definitely can be done in many ways. …
(위 내용은 AN INTRODUCTION TO Programming and Numerical Methods in MATLAB에서 일부 발췌했음을 알려드립니다)


간단히 얘기하면 다음과 같습니다

f(x) = 0 를 만족하는 x를 찾기 위해

주어진 방정식 f(x) = 0 를 g(x) = x 의 형태로 바꾸어서 고려하겠다는 말입니다

이 때 사용하는 것이 fixed point( 2차원 평면에서 y = x 직선 위에 있는 임의의 점 )입니다


이 iteration의 알고리즘을 간단히 보면 다음과 같습니다
x_0 : initial guess

x_{n+1} = g(x_n)

다시말하면, 초기값을 g(x)의 input으로 집어넣으면 나오는 output이 있는데,
그것을 다시 g(x)의 input으로 집어넣는 일을 반복하는 것입니다



그러면 이제,
우리의 관심사가 g(x)를 어떻게 찾을것인가? 로 바뀌었습니다

그런데 사실 g(x)를 만드는 작업 자체는 그다지 어렵지 않습니다


가장 간단히 만들 수 있는 g(x)는 x - f(x) 입니다

g(x) = x - f(x) = x   ⇔   - f(x) = 0   ⇔   f(x) = 0

이 외에도 f(x)의 모양에 따라 충분히 다양한 모양의 g(x)를 만들 수 있습니다

하나의 g(x)만으로 근을 찾을 수 있는 것이 아니기 때문에 같은 iteration이라도 g(x)는 다를 수 있습니다
이 때 g(x)를 이상한 모양으로 잡게 되면, 근이 존재하는데도 불구하고 이 iteration으로 찾을 수 없는 경우도 있습니다


그래서 g(x)를 조금 더 잘 잡기 위해 다음과 같은 정리를 사용합니다
함수 g와 초기 추정값 p0가 다음을 만족할 때,
만약 [a,b] 안의 모든 x에 대해 |g'(x)| < 1 이면 이 iteration으로 근을 찾을 수 습니다

만약 [a,b] 안의 모든 x에 대해 |g'(x)| > 1 이면 이 iteration으로는 근을 찾을 수 습니다

용어에 대해 잠깐 설명하자면,
i)에서
C[a,b]는 구간 [a,b]에서 연속인 함수들을 모아놓은 집합 입니다

iii)에서
A를 뒤집은 것 처럼 생긴 이 ∀ 기호는 for all 또는 arbitrary 의 뜻을 가지고 있습니다


정리가 다소 복잡하게 쓰여있는 느낌입니다만,
간단히 정리하면 다음과 같습니다

g와 g'가 연속함수이고, 초기 추정값을 p0라고 했을 때,
|g'(p0)| < 1 이면 이 iteration으로 근을 찾을 수 있고
|g'(p0)| > 1 이면 이 iteration으로 근을 찾을 수 없습니다



f(x) = x² - 2, 초기 추정값 = 1 이라고 하고 두가지 예를 보시겠습니다
1. g(x) = x - f(x) = x - (x² - 2)

이 경우에 g'(x) = 1 - 2x 이므로 g'(√2) < -1 이지요
(g'(x)에 대한 계산은 보통 손으로 하는 작업이므로 이 때는 √2가 얼마정도인지 짐작하고 있다고 가정합니다)
|g'(√2)| > 1 이므로 위 정리에 의해 근을 찾을 수 없지만, 직접 눈으로 보면 아래와 같습니다
파란색 그래프가 f(x), 붉은색 그래프가 g(x), 검은색 그래프가 직선 y=x 입니다


2. g(x) = 1 + x - x²/2

이 경우에는 g'(x) = 1 - x 이므로 g'(√2) ≒ -0.414 입니다
|g'(√2)| < 1 이므로 위 정리에 의해 근을 찾을 수 있고, 직접 눈으로 보면 아래와 같습니다
파란색 그래프가 f(x), 붉은색 그래프가 g(x), 검은색 그래프가 직선 y=x 입니다


둘의 차이가 보이십니까?

|g'(x)| > 1 인 경우에는 iteration을 수행할 수록 점점 근과 멀어지고,
|g'(x)| < 1 인 경우에는 iteration을 수행할 수록 점점 근과 가까워집니다

그래서 이 방법으로 근을 찾고자 할 경우
주어진 f(x)에 대해 적당히 g(x)를 잡아주는 것이 중요합니다



이제 코드로 구현한 것을 보시겠습니다

잘 보시면 maximum_iteration이라는 변수가 있습니다

위의 1번 예처럼 iteration을 수행할 수록 근과 멀어지는 경우
iteration을 무한히 반복하면 무한히 멀어지는데, 이걸 막아주기 위한 수단으로 반복 회수를 제한하는 방법을 사용합니다


또, 예전의 √2 포스트에서도 나왔던 tolerance가 있습니다

정해진 회수만큼 iteration을 수행하다가
두 x값의 차이가 허용오차보다도 작아지면 같은 값으로 간주하고 그 중 하나를 반환합니다


어떤 f(x)에 대해 이 코드를 이용하기 위해 g(x)를 잘 잡았는데도 불구하고 원하는 근이 나오지 않는다면
다음과 같은 조치를 취하시면 됩니다

1) maximum_iteration을 조금 더 크게 잡아주세요

1)을 했음에도 불구하고 답이 나오지 않습니다
⇒ 2) f(x)의 일부분이 삼각함수입니까? 그러면 g(x)를 바꿔주세요
삼각함수의 모양때문에 원하는 근 ±(k×pi) 꼴의 근이 나올 수도 있습니다 -_-;



이번 포스트는 여기까지입니다//

(포스팅 소요시간 : 약 80분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 1  (8) 2009.01.17
Matrix Decomposition  (1) 2009.01.08
무리수 √2의 값을 구해보자! : Part 5  (3) 2008.12.27
Interpolation : Part 3  (12) 2008.12.05
Interpolation : Part 2  (0) 2008.11.28
Interpolation : Part 1  (11) 2008.11.15
posted by Milkskin

댓글을 달아 주세요

  1. 글 잘 보았습니다.^^

    제 짧은생각입니다만.. 위의 방법이 뉴턴근사법과 비슷한 맥락으로 문제를 해결하나간 듯 싶습니다. 반복적인 알고리즘으로 점점 정답에 근접해가는 방법..

    근데 제가 머리가 나빠서 포스팅하신 글이 머리에 쏙 들어오지를 않네요..ㅠㅜ 아무래도 좀더 들여다봐야 할 듯 싶습니다.

    좋은 글 감사합니다..^^

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.12.27 20:44  Addr Edit/Del

      Mr.K의 글은 팀블로그 내에서도 같은 수학과인 Sparking도 이해하지 못한답니다 -ㅁ-...;;

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.28 03:40  Addr Edit/Del

      네 맞습니다 ^^

      Part 1에 소개된 Bisection Method나
      Part 4에 소개된 Secant Method 역시

      반복을 통해 원하는 답에 근접해가는 알고리즘을 가지고 있지요~


      포스팅을 이해하지 못하시는건.. 음;

      아직 제 문장력이 많이 부족하여 그런 것 같습니다;
      앞으로는 조금 더 깔끔하게 설명할 수 있도록 노력하겠습니다 (__)


      댓글 감사합니다 ^^


안녕하십니까 Mr. K입니다

목요일에 글을 쓰기 시작하는것도 오랜만이군요
과연 목요일이 끝나기 전에 글을 올릴 수 있느냐가 문제지만 -_-;


지난 두 포스트에 이어서 계속 같은 데이터( 3개의 점: (1, 2), (2, 3), (3, 6) )를 가지고 얘기해보겠습니다

…. We remark that various conclusions can be drawn from the data by using the forward differences; for instance whether it was generated using a polynomial (in which case the differences truncate).
We now construct a polynomial which goes through a set of points which are not necessarily evenly spaced. Let us consider the polynomial

It is worth pausing at this point and checking that this curve goes through each of the points (x_j, f_j). For example for j = 3, we set z = x_3 and only the third term is non-zero and we have

Hence the value of the polynomial at z = x_3 is f_3 (as we would hope). This is an example of a Lagrange polynomial; which could have equally been written as

This is a convenient way to write out the cubic we require (as it is relatively easily extended to higher-order cases) and in order to evaluate it we can use the MATLAB code: …
(위 내용은 AN INTRODUCTION TO Programming and Numerical Methods in MATLAB에서 일부 발췌했음을 알려드립니다)


영어로 뭐라고 막 쓰여있지만 가볍게 무시해줍시다 -_-;


주어진 순서쌍의 집합에는 (x_n, f_n)꼴의 점들이 있는데, '주어진 N+1개의 점을 지나는 N차 다항식'을 구하기 위해

첫번째 그림에 있는 것과 같은 모양의 다항식을 생각합니다

그러면 저 다항식은 두번째 그림의 예와 같이 f(x_n) = f_n 이라는 관계를 갖게 됩니다

이러한 다항식을 Lagrange polynomial이라고 부르고 세번째 그림과 같이 줄여서 씁니다


책에서는 4개의 점을 예로 들어서 다항식을 소개하였는데,

이것을 'N개'의 점에 대해서 확장시키면 다음과 같습니다

N개의 점에 대한 N-1차 Lagrange polynomial.


N+1개의 점에 대해서 확장시키려면 위의 N 자리에 N+1을 대입하기만 하면 됩니다

책에서는 N개의 점에 대해서 소개하고 있지만, 저는 보간법 포스팅을 N+1개의 점에 대해서 시작했기 때문에
설명하는 내용과 등장하는 수식 간에 다소 차이가 있을 수 있습니다

이 공식을 우리의 데이터: (1, 2), (2, 3), (3, 6)으로 적용해보면 다음과 같습니다



다소 계산은 복잡합니다만
지난주에 포스팅했던 Newton Forward Differences 와 비교했을 때 훨씬 '단순한' 모양을 하고 있습니다

수업시간에 들은 내용이 잘 기억나지 않지만, 이 다항식의 단점은 딱히 없었던 것 같습니다
굳이 단점이라 할만한 것이 있다면 손으로 계산하기 귀찮다는 것이랄까 -_-;
(개인적인 생각이지만, Vandermonde matrix >> Lagrange polynomial > Newton Forward Differences 순으로 귀찮은 연산인 것 같습니다 -_-;)


코드로 구현해보면 다음과 같습니다


위의 소스에서 combination이라는 함수는 Newton Forward Differences에 썼던 것을 그대로 가져왔습니다

numer라는 함수는 다항식의 계수부분 중 분자(numerator) 부분을 구하는 함수이고,
(정확히 말하면 분자를 모두 구하는 것은 아니고, 위의 공식에서 f_i 를 제외한 나머지부분에 대한 분자를 구합니다)

denom이라는 함수는 다항식의 계수부분 중 분모(denominator) 부분을 구하는 함수입니다


이제 우리의 데이터: (1, 2), (2, 3), (3, 6)을 가지고 프로그램을 실행한 결과는 아래와 같고,



다른 case를 테스트하기 위해 적당히 4개의 점을 입력한 결과는 아래와 같습니다




이번주 포스트는 이것으로 마치고,
다음주는 시험기간이라 한 회 쉬게 될 것 같습니다

더불어, 요즘 pku 3685: matrix 를 풀어보고있는데, 잘 안됩니다
AC받은 2人은 시간 나는대로 서로 상의를 하든지 해서 나 군입대 하기 전까지 풀이를 올려주길//
Talk카테고리에 미리 얘기했던 것처럼 명확한 이유가 없다면 태클 마구 들어갈겁니다 -_-;

(포스팅 소요시간 : 약 65분 + 서버점검 8시간 + 5분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix Decomposition  (1) 2009.01.08
무리수 √2의 값을 구해보자! : Part 5  (3) 2008.12.27
Interpolation : Part 3  (12) 2008.12.05
Interpolation : Part 2  (0) 2008.11.28
Interpolation : Part 1  (11) 2008.11.15
R.A.M. #1. 무리수 √2의 값을 구해보자! : Stage 4  (2) 2008.10.31
posted by Milkskin

댓글을 달아 주세요

  1. .... 매트릭스 풀이는 고려해보도록 하겠심. 그나저나 이런 풀이를 코드로 옮기다니.. 역시 곽은 -_-

  2. Favicon of http://blog.naver.com/cowsbow BlogIcon Seez 2010.05.23 20:15  Addr Edit/Del Reply

    좋은 내용 감사합니다.
    저는 라그랑지 함수 틀 안에 x값을 집어넣어서 y값을 나오게 한 후
    그것을 프로그램 폼 안에 픽셀로 찍어서 그래프를 보여주려고 하는데
    public int[,] point = new int[20, 2];
    public double ragrange(int x)
    int i, k, n;

    double total1 = 1, total2 = 0;

    n = count - 1;

    for (k = 0; k <= n; k++)
    {
    ..........for (i = 0; i <= n; i++)
    ..........{
    ....................if (i == k)
    ..............................break;
    ....................total1 *= (x - point[i, 0]) / (point[k, 0] - point[i, 0]);
    ..........}
    ..........total2 += total1 * point[k, 1];
    }
    return total2;


    라그랑지 반복식의 형태로 틀을 짜고 고치고 햏봐도
    함수식이 잘못되었는지.. 제대로 안나옵니다
    x값은 -200부터 200까지 계속 불러오는데
    함수 모양은 오류 뜨거나 비정상적...이라서 ㅜㅜ
    >point 배열은 입력받은 점의 위치입니다.

    • Favicon of http://cm4st.tistory.com BlogIcon Mr.K 2010.05.24 23:38  Addr Edit/Del

      소중한 댓글 감사합니다 :)

      이 포스트를 작성한지 거의 1년 반만에 다시 봤더니
      제가 썼던 글이지만 무슨말인지 못 알아들을뻔 했습니다 -_-;


      Seez님의 함수에서는 두가지부분이 문제가 되는데요

      첫번째로,
      안쪽 for문에서

      if( i == k ) break;
      이라고 써주셨는데
      break 대신 continue를 써주시면 되겠구요 :)

      두번째로,
      바깥쪽 for문에서

      안쪽 for문 들어가기 직전에
      total1을 1로 초기화해주는 부분을 새로 써주시면 될 것 같습니다


      다시 말해서,

      (전략)
      for( k = 0; k <= n; k++ )
      {
      ........// 이부분에 total1 = 1;
      ........for( i = 0; i <= n; i++ )
      ........{
      ................if( i == k )
      ........................break; // 이부분을 break 대신 continue로
      ................total1 *= (x - point[i, 0]) / (point[k, 0] - point[i, 0]);
      (후략)

      이렇게 고쳐주시면 잘 돌아갈 것 같습니다 '-';

  3. Favicon of http://blog.naver.com/cowsbow BlogIcon Seez 2010.05.26 13:37  Addr Edit/Del Reply

    아 감사합니다 초기화를 안하다니... 그런 초보적인 실수를 -_-;
    if문은 제가 함수 이해를 잘못한거같네요.
    if (i != k) 이것으로 바꿨어요 ㅎ
    해결하니 또다른 문제가 생기네요 ㅜㅜ 아무튼 감사합니다.

    • Favicon of http://cm4st.tistory.com BlogIcon Mr.K 2010.05.26 21:15  Addr Edit/Del

      if( i == k ) break;


      if( i != k ) break;
      으로 바꾸셨다는 말씀인가요?

      저는
      if( i == k ) continue;
      로 바꾸라고 해드렸습니다만 '-';;

  4. Favicon of http://blog.naver.com/cowsbow BlogIcon Seez 2010.05.26 21:40  Addr Edit/Del Reply

    아. 이 반복식의 조건이 i = 0 부터 n까지 이고
    i 가 k와 같지 않을 때 돌아야 되는 조건인데요
    그걸 잘못 이해해서 브레이크를 걸었어요 ;
    그래서
    if (i != k)
    .....total1 *= (x - point[i, 0]) / (point[k, 0] - point[i, 0]);
    이렇게 바꿧어요.

    • Favicon of http://cm4st.tistory.com BlogIcon Mr.K 2010.05.27 00:07  Addr Edit/Del

      아하//
      그렇게 바꾸셨다면 제가 의도한 것과 같겠습니다


      그런데 또다른 문제가 생겼다니 '-'; 어떤 문제인가요?

  5. Favicon of http://blog.naver.com/cowsbow BlogIcon Seez 2010.05.27 10:53  Addr Edit/Del Reply

    아니에요 ㅎ 그 문제는 해결 했어요
    라그랑지 그래프는 잘나오네요.. 다행히도 ;ㅂ;
    이제 뉴턴도 해봐야 @.@

    • Favicon of http://cm4st.tistory.com BlogIcon Mr.K 2010.05.28 20:32  Addr Edit/Del



      코딩하다가 잘 안되면 또 물어봐주세요 ^^;

  6. Favicon of http://blog.naver.com/cowsbow BlogIcon Seez 2010.05.29 18:07  Addr Edit/Del Reply

    뉴턴 함수를 만들었는데요
    http://postfiles4.naver.net/20100529_19/cowsbow_1275123473568KSKvm_jpg/제목_없음_cowsbow.jpg?type=w2
    여기 보이는 대로 대입한것을 만들었는데
    이 식이 아닌건지 아니면 소스가 잘못된건지.. 헷갈리네요 ㅜㅜ
    수학은 너무 어려워요!

  7. Favicon of http://blog.naver.com/cowsbow BlogIcon Seez 2010.05.29 22:22  Addr Edit/Del Reply

    어라라 크롬에선 안되고 익스에서 실행하면 되요... 크롬이 뭔가 문제있나 안되네용;;
    아니면 새창 띄워서 링크만 복사해서 해보심이..


안녕하십니까 Mr. K입니다

지난주에 한회 쉬었음에도 제 날짜에 포스팅을 하지 못해 뭐라 할 말이 없습니다 -_-;


지난 포스트(Interpolation : Part 1)에 이어서

같은 데이터( 3개의 점: (1, 2), (2, 3), (3, 6) )를 가지고 얘기해보도록 하겠습니다


이번에 얘기할 주제는 Newton Forward Differences 입니다

We shall now discuss the operation of fitting an Nth order polynomial through N + 1 points and remark again this will yield a unique answer. We consider the set of data points: (x_0, f_0), (x_1, f_1), …, (x_N, f_N). We now introduce the difference operator Δ such that

or in general

These are called forward differences, since points forward of the current value are used (there are also backward differences and central differences, which we shall meet in our discussion of the solution of differential equations). We consider the composition of the operator whereby


Of course we can now proceed to define Δⁿf_0 in an iterative manner.
We introduce the polynomial


which will ultimately terminate after N terms. Alternatively this can be written as:

… (5.1)

We consider the data values to be equally spaced, so the value of Δx_j is h ∀j. This analysis can be extended to irregularly spaced points, but we shall not attempt that here.
We are now able to construct the polynomial (5.1) for a set of points. We start with a simple …
(위 내용은 AN INTRODUCTION TO Programming and Numerical Methods in MATLAB에서 일부 발췌했음을 알려드립니다)


책에 쓰인 글을 그대로 옮겨온거라 오타가 있을지도.. -_-;


어렵게 쓰여있는 듯 하지만 실은 별거 아닙니다

먼저 difference operator Δ(delta라고 읽습니다)를 정의하는데, 이것은 주어진 순서쌍의 집합에서 '다음값 - 현재값'으로 정의합니다

그리고 Δ의 중첩은 세번째 그림와 같이 정의합니다


그리고나서 네번째 그림과 같은 다항식을 생각하게 되는데,
이것이 바로 우리가 구하고자 하는 '주어진 N+1개의 점을 지나는 N차 다항식'입니다

그것을 줄여서 쓴 것이 다섯번째 그림입니다

이때 h라는 변수는
주어진 순서쌍의 집합에서 x좌표를 기준으로 오름차순 정렬을 했다고 가정하고
'다음 x값 - 현재 x값'이 일정한 상수값을 가질 때 그 상수값을 h에 대입합니다



지난 포스트에서 미리 잡아둔 데이터: (1, 2), (2, 3), (3, 6)를 가지고 이것을 적용해보도록 하지요


우선 세 점의 x좌표는 1, 2, 3인데 이것은 오름차순으로 정렬되어있고, 따라서 '다음 x값 - 현재 x값'은 1이라는 고정된 값을 주게 됩니다
따라서 h = 1이고,

f_0와 Δf_0, 그리고 Δ²f_0는 위의 표에 계산이 되어있으니 공식에 적용해보도록 하겠습니다


간단하게 나오지요?

다만 단점이라면, h라는 변수를 정의하기 위해 주어진 데이터의 x값은 균일해야 한다는 것입니다
(위 지문의 마지막 부분을 보면 균일하지 않은 점에 대해서도 확장해서 적용할 수 있으나 여기서는 하지 않겠다라며 넘어갑니다)


이것을 코드로 쓰면 다음과 같습니다



이번 포스트는 이것으로 마치고,
다음주에 쓰게 될 포스트에서는 데이터의 x값이 균일하지 않아도 쓸 수 있는 Lagrange polynomial에 대해서 얘기하겠습니다

(포스팅 소요시간 : 약 75분)
posted by Milkskin

댓글을 달아 주세요


안녕하십니까 Mr. K입니다

2주 전까지 쓴 소재는 적당히 접기로 결정을 내린 터라, 다른 소재를 찾아야 하는데

소재가 없어서 늦게 찾았다기보단 그저 학교일이 바쁘네요 -_-;


그리고, 이전 소재에서 제목 앞에 붙여놓았던 R.A.M. 이 별로 의미가 없는 것 같아서

(R.A.M. = Realizable Abstract Matter or Material 이었으나, 이런걸 달아놓지 않더라도 수학적인 것에 대해 얘기를 하다보면 무의식중에 무한대나 무리수 등등, 컴퓨터에서 똑같이 따라하지만 실수에서 되는 계산이 깔끔하게 떨어지지 않는(예외는 있습니다, Maple이라는 프로그램은 √2를 입력하고 엔터를 치면 결과값에 그대로 √2가 출력이 됩니다) 경우가 많기 때문에 그냥 그때그때 해당하는 주제가 나오면 언급하기로 했습니다)

다시 마음이 바뀌기 전까지는 아마 '제목 : 연재회수' 꼴로 계속 적을 듯 합니다 ㅋ


그럼 시작해보지요



우리가 수학을 하다보면 종종 주어진 명제에 대해 '그 역도 성립하는가?' 를 따지게 되곤 합니다

아마 이 보간법(interpolation)이라는 것도 그렇게 출발해서 나온 것이 아닐까 생각해봅니다

어떤 함수 f(x)가 주어져 있을 때, 우리는 그 함수 위에 있는 몇 개의 점을 정확하게 집어낼 수 있습니다

그러면 반대로,
몇 개의 점이 주어져 있을 때, 그 점들을 완벽하게 지나는 함수를 찾아낼 수 있을까?

-라는 것이 이번 소재의 핵심 내용입니다


아래의 그림을 보시죠


좌표평면 위에 3개의 점이 있습니다

각각은 (1, 2), (2, 3), (3, 6)이라는 좌표를 가지고 있지요

3개의 점을 지나는 2차 다항식은 유일하게 존재합니다
(실제로 N+1개의 점을 지나는 N차 다항식은 유일하게 존재합니다, 이유가 궁금하다면 생각해보세요 :D)


그래서 함수 f(x)를 f(x) = a + bx + cx² 이라 놓고 아래와 같이 풀면



원하는 f(x) = 3 - 2x + x² 를 얻어낼 수 있습니다


그런데 사실,
고등학교과정까지만 잘 마치면 N+1개의 점을 지나는 N차 다항식도 연립방정식 풀듯이 풀어내서 구할 수 있습니다

다만 시간이 오래걸리고 계산 오차가 발생할 확률이 클 뿐.. -_-;

그래서 그 시간과 오차를 줄여주기 위해 새로운(?) 개념을 도입합니다



이 때, 위의 그림에서 다음과 같은 행렬을 Vandermonde matrix라고 합니다
(검색좀 때려보니 Vandermonde는 '밴더몽드'라고 읽는 것 같더군요)

n×n Vandermonde matrix, 책에 따라서는 이것의 transpose를 이것으로 칭하기도


이 행렬의 역행렬이 존재한다면, 다음과 같이 다항식의 계수를 구할 수도 있습니다



만약 주어진 N+1개의 점들의 x좌표들이 단 한 개도 중복되지 않는다면, N×N 밴더몽드 행렬은 행렬식이 0이 아니게 되고,
(이유가 궁금하다면 생각해보세요 :D 선형대수학을 배웠다면 금방 답이 나올겁니다)

역행렬을 구해서 위의 식처럼 계산하면 우리는 원하는 N차 다항식을 구할 수 있습니다


역행렬을 구하는 과정은 가우스-조르단의 소거법(Gauss-Jordan elimination)을 사용하였습니다
이것은 수식으로 보이지 않고 넘어가겠습니다 -_-;


이것을 코드로 쓰면 다음과 같습니다


그러나 이 방법의 단점은 구하고자 하는 다항식의 차수가 커지면 커질 수록 시간이 오래걸린다는 단점이 존재합니다

학술제 준비로 다음주 포스트는 쉬고, 다다음주에 올리게 될 포스트에서는
차수에 큰 영향을 받지 않고 빠르게 계산이 될 것 같은 Newton Forward Differences에 대해 얘기하겠습니다



덧. 크롬에서 그림파일 업로드하는 속도가 전에 비해 훨씬 빨라졌군요 -_-b

(포스팅 소요시간 : 약 110분)
posted by Milkskin

댓글을 달아 주세요

  1. 오차 2009.09.08 16:52  Addr Edit/Del Reply

    (31) Vandermond matrix 를 생성에서
    (34) double exp = 1;
    (35) for( j = 0; j < i%pairs; j++ )
    여기서
    i%pairs는 무슨 의미 인가요?
    그리고 왜 exp = 1 이라고 했는지 궁금합니당...
    잘 몰라서요...
    부탁드립니당.~~

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.09.08 17:48  Addr Edit/Del

      맨 마지막 부분에
      3개의 점을 이용해서 보간법을 실행해본 예시를 가지고 말씀드리겠습니다//


      Vandermonde matrix의 모양은 각 점의 x좌표에 의해 바뀌는 형태인데,

      이 포스트에서는 다음과 같은 형태를 띄게 될 것이나
      [1 1 1]
      [1 2 4]
      [1 3 9]

      실제 메모리에서는 [1 1 1 1 2 4 1 3 9]처럼 일렬로 놓이게 됩니다 -_-;

      즉,
      vander[0]~vander[2]는 exp에 xs[0]의 거듭제곱을 곱해야 하고,
      vander[3]~vander[5]는 exp에 xs[1]의 거듭제곱을 곱해야 하고,
      vander[6]~vander[8]은 exp에 xs[2]의 거듭제곱을 곱해야 합니다

      이 때, 배열 vander의 index를 3으로 나눈 몫을 xs의 index로 사용하면 그때그때 필요한 xs의 원소를 exp에 곱하겠지요

      단, exp를 1로 초기화하지 않으면
      exp는 초기값이 없는 상태로 있기 때문에 xs의 원소를 곱하는 것이 별 의미가 없습니다 -_-;
      (exp라는 변수는 34번째 줄에서 처음 선언하는 것입니다)


      그리고
      [1 1 1]
      [1 2 4]
      [1 3 9]
      이 형태에서 보시면
      1열은 xs의 각 원소들의 0제곱,
      2열은 xs의 각 원소들의 1제곱,
      3열은 xs의 각 원소들의 2제곱입니다

      하지만 위에서 말했듯이 메모리에서는 일렬로
      vander[0]~vander[8]까지 놓이게 되지요

      그런데 각 열의 index를 보면
      1열의 index는 [0], [3], [6],
      2열의 index는 [1], [4], [7],
      3열의 index는 [2], [5], [8]입니다

      각 열의 공통점은 '3으로 나눈 나머지가 같다'라는 점이죠

      따라서, 1로 초기화한 exp에 xs의 원소들을 곱하는 회수를 결정해주는 것이 i%pairs입니다 -_-;

      (중간에 잠깐 졸아서 글의 흐름이 매끄럽지 않을 수 있습니다 -_-;)

  2. 오차 2009.09.08 22:18  Addr Edit/Del Reply

    아~~감사합니다...그럼 한가지만 더 여쭤 볼께요...

    exp는 exponential 함수가 아니라 임의로 정해준 것인가요??

    아 그리고 죄송합니다. 하나만 더요...

    처음에 int pairs라고 정의를 했는데 이것이 의미하는것이 뭔가요??

    그리고 44줄에 %2는 뭔가요???

    죄송합니다...
    자꾸 초보적인 질문같은것만 해서...히힛
    좋은하루 되세용~

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.09.08 23:30  Addr Edit/Del

      네; exp는 변수명으로 사용된 녀석이라
      exponential함수와는 관계가 없습니다;

      단지 x좌표들의 거듭제곱을 계산하기 위해 만든 것인데,
      각 변수들의 역할을 알아보기 편하게 일부러 저렇게 쓴 것이죠 =_=;


      "int pairs"는 변수의 선언을 뜻합니다

      C언어에서 특정 변수를 사용하기 위해서는
      중괄호로 블록을 연 후 다른 연산을 하기 전에 미리 선언을 해야 합니다
      (다른 언어들도 있지만 여기서는 패스 :D)

      앞의 int는 "4바이트짜리 정수형 자료"를 뜻하며,
      뒤의 pairs는 변수명입니다

      int 외에도
      "1바이트짜리 문자형 자료"인 char, "2바이트짜리 정수형 자료"인 short,
      "4바이트짜리 실수형 자료"인 float, "8바이트짜리 실수형 자료"인 double 등이 있습니다 -ㅠ-;


      44번째 줄에 나오는 %2는 "나머지 연산자"라는 것입니다

      일반적인 산술 연산에는 덧셈(+), 뺄셈(-), 곱셈(×, *), 나눗셈(÷, /)이 있습니다만
      C언어에는 추가로 나머지를 구하는 연산이 있습니다
      그리고 그 나머지 연산자가 %입니다

      정수형 자료의 특성상
      나눗셈을 했을 때, 그 결과값은 몫으로만 나오게 됩니다
      즉, 20/3의 결과는 6이 되는 것이죠

      나머지 연산자를 이용해서 20%3의 결과를 알아보면 2가 나오게 됩니다
      다만, 음수에 대해 나머지 연산을 했을 경우 그 결과도 음수가 나옵니다

      -20%3의 결과는 -2가 나오지요 -_-;;

  3. 오차 2009.09.09 11:53  Addr Edit/Del Reply

    음....31부터 40까지는 어떻게 해석이 되는 건가요??

    특히 37줄에 i/pairs 이거는
    나누기를 의미하는거 맞는거죠???

    부탁드려요..

  4. 2009.09.09 16:24  Addr Edit/Del Reply

    비밀댓글입니다

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.09.09 17:09  Addr Edit/Del

      음 =_=;


      혹시 네이트온 하시나요?;

      질문에 대한 답을 하기 위해서는 컴터 앞에 앉아있어야 가능할 것 같습니다 =_=

      violent-ame@nate.com 에다 쪽지보내주세요~

  5. 2009.09.15 14:06  Addr Edit/Del Reply

    비밀댓글입니다

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.09.15 20:53  Addr Edit/Del

      방정식의 형태로 나타내는 것은 출력의 방법을 바꾸면 되므로

      114번째 줄부터 121번째 줄까지의 내용을 적절하게 수정해주시면 됩니다;


      그리고 현재 이 소스에는 그래프까지 그려주는 기능은 없습니다;

      저도 아직 그래프를 그리도록 만들 수는 없는지라 =_=;

  6. 헉. Ax = b <=> [A|b] -> [E|x]를 소스로 구현하셨군요.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.09.23 01:22  Addr Edit/Del

      네 그렇습니다~

      모든 케이스에 대해서 적용이 되는지 실험해보진 않았으나
      일단 vandermonde matrix에는 적용이 되도록 만든 소스입니다 =_=;

부제(?) : 글쓰는건 목요일에 시작했다는 -_-;


안녕하십니까 많이 늦었습니다//

원래 저녁먹고 한숨 잤다가 깨서 포스트를 미루는 공지를 썼었는데

잠이 다 깨고 나니 오늘 안에도 쓸 수 있을 것 같아(& 댓글 달린것도 없어서) 올렸던 공지를 내렸습니다


..만;

결국 자정을 넘기고 마네요 -_-;



Bisection Method(RAM 1-1)에서
Dlbo군이 댓글로 Newton's Method(이하 뉴턴메소드)를 언급해서 그것에 대해 쓸까 했지만


그건 도함수가 필요하니 환타군이 쓰기엔 아직 좀 무리가 있을 수 있지요;
또, 도함수를 쉽게 구할 수 없는 함수도 많습니다 -_-;



그리고 뉴턴메소드의 경우, 함수가 잘생겼다면 상관없지만
함수가 못생겼다면, 초기값(x0)을 실근의 추정값에서 멀리 잡을수록 발산할 확률이 높습니다 -_-;

그래서 나온 방법인지는 잘 모르겠는데,
최근 수업시간에 배운 Secant Method를 소개해볼까 합니다



뉴턴메소드는 주어진 초기값(x0)에 대해 다음 근사값(xn)을 계산하기 위해
위 그림에서 보시는 것 처럼 f'(x(n-1))이 필요합니다

그런데 이 f'(x(n-1))의 정의는 다음과 같으므로, 정의부분에서 '극한'만 떼어낸 근사값을 생각하는겁니다


저 근사값이 작은 오차를 가지기 위해서는 x가 x(n-1)에 가까울 수록 좋은데,
우리가 가지고 있는 정보는 x0, x1, …, x(n-2), x(n-1)이므로

저 x에 x(n-2)를 대입한 값을 최종 근사값으로 생각합니다

그러고나서 이 최종 근사값을 f'(x(n-1))에 대입하기만 해주면, 우리는 다음과 같은 Secant Method를 얻어낼 수 있습니다




이 때, 두 초기값 x0와 x1은 함수의 정의역 안에 있기만 하면

min(x0, x1) < 실근의 추정값 < max(x0, x1)을 만족한다는 조건 하에 아무렇게나 잡아도 되는 것 같습니다

따로 도함수를 구할 필요도 없으니 (식이 좀 복잡할 수 있지만) 적용하는 데도 큰 무리가 없습니다



위 코드에서 secantMethod함수 내의 terms라는 변수는 '최대시행회수'를 나타냅니다



이제 Secant Method를 사용해서 √2를 구하는 과정을 그래프로 보여드리고 포스팅을 마치도록 하겠습니다//
아마 다음주에는 다른 주제를 가지고 포스팅할 것 같지만 그게 뭐가 될지는 저도 잘.. -_-;


먼저, f(x) = x² - 2 라 하고 시작합니다

x0와 x1은 제 임의로 x0 = 2, x1 = 1이라 하였습니다

위 그래프에서 파란색 *가 실근(√2)입니다

주어진 공식에 의해 x2를 구해보면 4/3, 즉 1.3333…이 나옵니다
실제 √2와 약 0.08088정도 차이납니다

주어진 공식에 의해 x3을 구해보면 10/7, 즉 1.4286…이 나옵니다
실제 √2와 약 0.01436정도 차이납니다

주어진 공식에 의해 x4를 구해보면 41/29, 즉 1.4138…이 나옵니다
실제 √2와 약 0.00042정도 차이납니다

(포스팅 소요시간 : 약 60분)
posted by Milkskin

댓글을 달아 주세요

  1. 어쩐지, 니가 왠일로 목요일이 지났는데 포스팅이 안올라오나 했더니 공지를 내리고 쓰고 있던거였구나 ㅋㅋ..
    코드에서, '양의 제곱근을 구하고 싶은 소수를 입력해줏메'는 고의적 오타인거? ㅋㅋ

부제 : 나라면 10개를 다 갖겠어! (?)

어느 날, 조금 수상해보이는 남자가 당신에게 금화 10개를 주면서

"이 중에 가짜가 하나 있는데, 양팔저울을 3번만 사용해서, 가짜가 어느 것인지 그리고 가짜의 무게가 다른 것들에 비해 어떠한지 맞추면 9개의 진짜를 드리겠습니다"

-라고 말했다면, 당신은 이 문제를 어떻게 풀어낼 것인가?
(이런 스토리가 있어야 왠지 당위성이 있을 것 같아서.. -_-;)


안녕하십니까 Mr. K입니다

다음주가 시험이라 딱히 자료수집같은 것을 하지 못한 관계로, 이번 주는 '놀이'로 대체합니다

같은 이유(시험)로, 다음주 목요일에는 포스팅을 하지 못할 것 같습니다


이 문제는
제가 고등학교 다니던 때, 친구한테 물음을 받아서 하루이틀정도 머리를 굴리게 만들었던 문제입니다

작년에 C를 배우고나서 문득 이게 생각나서 코딩을 했었는데, 어찌어찌 하니까 되긴 되더군요 -_-;

(작년에 만들어서 완성한 그대로의 소스입니다, 아주 거칠죠, 띄어쓰기나 (변수에 대한)주석도 전혀 없고 ㅋㅋㅋㅋ)


그리고 위의 소스를 바탕으로 아래의 순서도를 그렸는데, 그걸 보고 dlbo군이 반해서(?) 전과를 요구하기도..
(분명 순서도를 먼저 그리고 코딩한게 아닌데 왜 -_-)


뭐 어쨌든, 이번 포스트의 목적은 '다른 팀원들이 이 문제를 풀고 그것이 정답인 경우, 스크린샷같은걸로 올려주었으면-'입니다
(물론 저는 풀이를 압니다)

위의 소스 말고,
오늘 갓 만든 아래의 소스를 가져다가 문제를 풀어주세요 :D


그럼 이만 마치겠습니다

아마 다다음주 포스트는 √2를 한번 더 가거나 다른 주제를 얘기하거나 할 것 같습니다

(포스팅 소요시간 : 약 55분)


*주
1. 제목은 제가 임의로 지은 것입니다
2. 부제 밑의 이야기도 제가 임의로 지은 것입니다 -_-;
3. 소스의 저작권은 제게 있습니다, 가져다 푸는 것은 권장하지만 자기 것이라 우기진 마십쇼

posted by Milkskin

댓글을 달아 주세요

  1. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.10.17 12:27  Addr Edit/Del Reply

    뭐... 뭐지. 저 거대한 플로우 차트는????

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.18 00:59  Addr Edit/Del

      ㅋㅋ 위에 있는 거친 소스를 그대로 옮겨놓은 순서도임 ㄷㄷ

  2. ㅋㅋㅋ 전과....ㅎㅎ

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.18 00:59  Addr Edit/Del

      ㅎㅎ 하지만 컴공 수업을 들어보니 전과는 안하는 편이 나은듯 -_-b

  3. 빌드해서 나온 실행파일도 동봉해줬음 좋았을텐데 말여.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.18 01:00  Addr Edit/Del

      음? 그런가?

      그냥 저거 copy to clipboard 해서 붙여넣고 실행하면 되는거 아닌가?;

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.10.18 01:36  Addr Edit/Del

      항상 컴파일러가 있는 컴에만 있는건 아니잖남 ㅡ,.ㅡㅋ 그리고 이 블로그에 그냥 놀러오는 일반 독자들도(있을라나...) 고려해줘야지 ㅡ,.ㅡ

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.18 11:55  Addr Edit/Del

      근데 그 실행파일로 돌리면

      결과가 나오면서 창이 닫히던데 -_-;

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.10.18 13:14  Addr Edit/Del

      conio.h를 인클루드 시키고 프로그램 종료 직전(메인함수 리턴 직전)에 getch();박아주면 아무키나 누를 때 까지 프로그램 안꺼지고 버티고 있지.

    • Favicon of http://zfanta.com BlogIcon  환타 2008.10.18 16:40  Addr Edit/Del

      cmd에서 하면 되지 말입니다.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.18 21:20  Addr Edit/Del

      conio.h랑 getch 했는데 소용없더라 -_-;


      아, cmd에서 되는걸 잊고 있었네요 ㅋ
      실행파일 첨부해야겠다는//

부제 : 글올리기도 바쁜데 부제는 무슨 부제 ㅋㅋㅋ

Continued Fractions

… from Section 2.5, (√5 + 1)/2 and √2 can be written as continued fractions. In fact, this is true for any real number. But to begin with, there are a number of types of continued fractions. We will briefly study simple continued fractions, that is, expressions of the type


denoted by <x0, x1, x2, …>, where x0 ∈ Z and xn ∈ N ∪ {0} for n ∈ N. If xn = 0 for all n > m ∈ N and xm ≠ 0, then the simple continued fraction is said to be finite, is denoted by <x0, x1, x2, …, xm>, and represents a rational real number. A simple continued fraction that is not finite is said to be infinite, and a converging infinite continued fraction is always represented by an irrational number. …
(위 내용은 A Friendly Introduction to ANALYSIS 2/e에서 일부 발췌했음을 알려드립니다)


연분수란, 위의 그림에서 보시는 것처럼 생긴 녀석들을 말합니다

연분수는, 첫째 항은 임의의 정수로 두고 둘째 항부터는 음이 아닌 정수로 구성된 수열로 표현할 수 있습니다
이 때, 1보다 큰 어떤 m에 대해서 xm까지는 0이 아니다가 x(m+1)에서 0이 된다면 그 연분수는 유한하다고 얘기하고 이것은 유리수를 나타냅니다

이런 유한한 연분수를 제외한 나머지 연분수를 무한하다고 얘기하고, 이것은 무리수를 나타냅니다


유한한 연분수의 예, 책에 따라 < > 대신 [ ]로 표기하기도


이 연분수를 가지고도 √2의 근사값을 구할 수 있습니다

단, 한가지 알아야 할 것이 있는데, n ≤ √2 < n+1을 만족하는 정수 n을 알아야 합니다
그러한 n을 첫째 항 x0에 대입합니다(여기서는 1이겠죠)

그리고나서 (√2 - x0)의 역수를 생각하는데(∵ 맨 위에 있는 그림에서의 형태와 같게 만들기 위해서입니다)

n' ≤ (√2 - x0)의 역수의 분모 < n'+1을 만족하는 정수 n'을 찾아서 x1에 대입합니다

그리고 또 ((√2 - x0)의 역수의 분모 - x1)의 역수를 생각하고, 이런 식으로 √2를 연분수 수열*로 표현할 수 있습니다



그런 과정을 거치고 나서 얻은 수열에 대해
마지막 항부터 역순으로 계산을 해주기만 하면 우리가 원하는 값을 얻을 수 있습니다




글을 읽어보시면서
'왜 연분수로 늘어놓았다가 다시 역순으로 계산을 할까? 귀찮게' 라고 반문하실 분이 있을지도 모르겠습니다만

지금 우리는 정확한 값을 모르는 무리수 x를 들고 있습니다
그러나 이 x가 어떤 정수 n에 대해 n ≤ x < n+1임을 알고 있습니다
그리고 우리는 가장 기본적인 사칙연산(여기서는 특히 나눗셈)을 할 줄 알고 있습니다

그래서 이 x를 조금 눈에 보이도록, 손으로 얼추 계산할 수 있도록 만들어주는게 '수열로의 변환'입니다

그렇게 변환한 수열을 연분수꼴로 쭉 써놓고
분수꼴을 유지하며 역순으로 계산한 후에, 마지막으로 나오는 분수의 분자·분모에 대해 나눗셈을 해주기만 하면 됩니다



많이 늦었네요

다음부터는 미리 포스팅을 해놓고 편하게 드라마를 보든지 해야겠습니다 -_-;

(포스팅 소요시간 : 한 번 날려먹은거 빼고 약 55분)


*연분수 수열: 정확한 명칭(딱히 있는 것 같지도 않지만)을 몰라서 그냥 저렇게 씁니다
posted by Milkskin

댓글을 달아 주세요

  1. 그 n도 함께 찾을 수 있는 방법은 없는겐감?-_-/

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.12 10:30  Addr Edit/Del

      ㅇㅇ 지금으로선 그냥 for문같은걸로 노가다 해야할듯?

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.10.12 11:50  Addr Edit/Del

      생각해봤는데 그럴 필요 없을꺼 같다. 무리수를 구하고 싶은 수에 sqrt 씌우고 자리버림 하면 되긴 한데.... 그럴 바에 그냥 sqrt로 구하는게 나은가?-_-?;

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.12 13:01  Addr Edit/Del

      ㅇㅇ; sqrt를 구하는 과정에 sqrt가 필요하다는 것 자체가 모순이지 -_-;

부제 : IE 7.0으로 바꿨는데 이미지 업로드가 안되네.

제곱근의 계산법

피타고라스에 의해 알려진 무리수 √2는 1.41421356…이다. 이 숫자를 쉽게 암기하는 방법은 각자의 요령에 달려 있다. 그런데 이 숫자가 어떻게 나오게 되었을까? 여기에서 제곱근의 계산방법을 알아보기로 하자.


0. 나눗셈의 그것과 비슷하도록 제곱근 기호를 길게 그리고 그 안에 2를 쓴다.

1. 제곱해서 2가 되거나, 모자르지만 그에 가깝게 되는 최대의 수는 1. 그러므로 B1과 C1(그림에 적어놓진 않았지만 몫부분에 해당함, 이하 Ck)에 1을 넣고 B1과 C1을 곱한 결과를 A2에 쓴다.

2. (A1-A2)는 1. 따라서 A3에 1을 넣고 00을 내려오게 한다.
3. B1 밑의 B2에 C1과 같은 1을 넣고 B1과 B2를 합한 값을 B3에 쓴다.

4. 2□×□가 100이 되거나, 모자르지만 그에 가장 가깝게 되는 □를 생각한다. 여기서는 4를 넣으면 24×4=96이 되어 가장 가깝다. 그래서 B3은 24, C2에는 4가 들어간다. 그리고 이 둘의 곱을 A4에 넣는다.

5. 이렇게 하여 B4에 C2와 같은 4를 넣고, 둘의 합계 28을 B5에 써넣는다.
6. 이런 식으로 똑같이 써넣어가면 차례차례로 제곱근을 구할 수 있다.


위에 제시된 그림처럼 계산을 하면 소수점 이하 1만 자리, 2만 자리라도 시간이 허용할 경우 세밀히 구할 수가 있다.
(위 내용은 '수학통이 되는 책'에서 일부 발췌했음을 알려드립니다)
(본문에서는 다소 설명이 부족한 것 같아 글수정을 조금 하였고, 그림은 포토샵으로 직접 그렸습니다)


Mr. K입니다

어제는 갑작스레 나갔다 올 일이 생겨서 오늘에서야 포스팅을 하게 되었습니다;


대략적인 방법은 위에 다 써놓았으니 코드로 구현한 것을 보도록 하겠습니다


지난번의 Bisection Method와 비교해보면 tolerance는 필요하지 않습니다

단지 소수점 이하의 자리수를 정하는 precision만 필요할 뿐이지요


pow10함수는 10의 거듭제곱을 반환하는 함수이고,

squareRoot함수는 제곱근을 구하는 함수입니다
left는 위 그림의 Bx부분에 해당하고,
right는 위 그림의 Ax부분에 해당합니다
extend는 ●□×□꼴의 계산과정중의 Bx부분에 해당합니다

이번에도 squareRoot함수의 body부분에 대한 설명은 필요 없으리라 생각합니다


혹시나
이 방법을 이용해서 손으로 제곱근을 구해보고 싶은 분들을 위해
√2 외에 √6을 구해보면 아래와 같습니다



오늘의 포스트는 이것으로 마칩니다

다음번에는 또 다른 방법으로 √2를 구하는 방법을 가지고 돌아옵니다 (__)

(포스팅 소요시간 : 두 번 날려먹은거 빼고 약 40분)
posted by Milkskin

댓글을 달아 주세요

부제 : 미정

Location of Roots Theorem

Let I = [a, b] and let f : I → R be continuous on I. If f(a) < 0 < f(b), or if f(a) > 0 > f(b), then there exists a number c ∈ (a, b) such that f(c) = 0.
(위 내용은 INTRODUCTION TO REAL ANALYSIS 3/e에서 일부 발췌했음을 알려드립니다)


안녕하십니까 Mr. K입니다

지난 주까지 무사히(?) '재귀 vs. 반복'의 포스팅을 끝내고 새로운 주제를 가지고 돌아왔습니다

포스팅 계획서에 언급해두었던 '무한의 범주에 있는 것을 유한하게 구현'하는 것을 하려고 합니다

그 첫 대상은 '무리수'가 되겠습니다

무리수라는 놈이 가진 특성이..
'정수부.소수부'의 형태로 표현할 때 소수부의 길이가 끝나지 않는다는 것이 있죠 (ex. π(pi) = 3.1415926…)

이것을 유한하게 구현해본다는 것은 그 근사값을 구해보겠다는 말과 같습니다

앞으로 얼마나 더 많은 주제를 다룰 수 있을지는 모르겠으나,
이 RAM계열의 포스트는 같은 목표를 가지고 쓰여집니다

이런 무한의 범주에 있는 것들을 얻기 위해 수학 라이브러리 함수로 계산했을 때의 결과에 근접한 값을 얻어내는 것



잡설은 그만하고, 이제 처음 써놓은 정리(이하 LRT라 하겠습니다)를 보도록 하죠

어떤 함수 f가 구간 [a, b] 위에서 연속이고 f(a) < 0 < f(b) 또는 f(a) > 0 > f(b)를 만족하면 f(c) = 0인 어떤 수 c가 구간 (a, b)안에 존재한다

즉, 간단히 말하면
구간 위에서 연속인 함수에 대해 양 끝 함수값의 부호가 반대라면, 구간 어딘가에 함수값이 0이 되는 점이 최소 하나는 있다는겁니다

그림으로 보시죠


사용자 삽입 이미지


이것을 보시면
함수 f는 구간 [0, 2]에서 연속이고, f(0) < 0 < f(2)를 만족하므로 f(c) = 0인 c가 구간 (0, 2) 안에 존재합니다

딱히 부정하려해도 x가 0.75 근처에 있을 때 y가 0 근처에 있다는게 눈에 보이실겁니다

그런데 눈으로 봤을 때,
x가 0.75 근처에 있다는건 알겠는데 정확한 값이 뭔지는 모르겠다는게 문제인겁니다

여기서 쓸 수 있는 방법이 바로 Bisection Method인데, 오늘 포스트의 가장 중요한 물건이라 할 수 있겠습니다

그것이 무엇인고 하니,

LRT를 만족하는 구간에 대해 계속해서 LRT를 만족하도록 구간을 반으로 줄여나가는 method입니다

위 그림에 대해 적용해보면

[0, 2]에서 LRT를 만족하고 있습니다

⇒ f(1)이 양수이므로 f(0)과 묶어서 보면 LRT를 만족합니다

⇒ 구간을 [0, 1]로 줄입니다, 여전히 LRT를 만족하고 있습니다

⇒ f(0.5)가 음수이므로 f(1)과 묶어서 보면 LRT를 만족합니다

⇒ 구간을 [0.5, 1]로 줄입니다, 여전히 LRT를 만족하고 있습니다

⇒ …

이 과정을 반복하면 우리는 정리에 언급되어있는 c를 반드시 찾을 수 있습니다



무리수 √2를 구하는 데 이게 왜 필요한가 싶을만큼 상관없어보이는 내용을 얘기했습니다만,

√2를 구하는 방법은 다음과 같습니다

1: x = √2 라 놓는다

2: 양변을 제곱하면 x² = 2를 얻는다

3: 우변을 이항하면 x² - 2 = 0을 얻는다

4: 함수 f를 f(x) = x² - 2로 잡고 f(c) = 0이 되는 c를 찾는다

감이 오십니까?

저렇게 만든 함수 f에 대해 적당한 구간을 잡고 Bisection Method를 써주기만 하면 우리는 원하는 √2의 근사값을 얻을 수 있습니다

아래의 그림을 참고하세요 (점점 줄어드는 구간을 보실 수 있습니다)


사용자 삽입 이미지


코드로 구현한 것은 다음과 같습니다



이 코드의 경우 임의의 실수에 대해 제곱근을 구할 수 있도록 해놓았습니다
그냥 2를 입력하면 √2의 근사값이 나오겠죠

함수들에 대해 설명을 하면
f는 위에서 언급한 함수 f와 같다고 보시면 되고,
absolute는 절대값을 구하는 함수,
sign은 input의 부호에 따라 다른 값을 리턴하는 함수이고,
마지막의 squareRoot는 제곱근을 구하는 함수입니다

전역변수 둘 중 하나인 realNumber는 제곱근을 구하고 싶은 수를 저장하기 위해 만든 것이고
나머지 하나인 tolerance는 '허용오차'를 나타냅니다

Bisection Method를 사용하면 '이론적으로'는 c값에 다가가지만
이 '다가간다'라는 말의 의미가 모호하기 때문에
실제 적용시에는 허용오차를 두어서 '그 허용오차보다도 오차가 작아지게 되면' 두 값이 같다고 보는겁니다

squareRoot함수의 body부분에 대한 설명은 패스하겠습니다


사용자 삽입 이미지


오늘의 포스트는 이것으로 마칩니다

다음번에는
다른 방법으로 √2를 구하는 방법을 가지고 돌아오겠습니다 (__)

(포스팅 소요시간 : 약 85분)
posted by Milkskin

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.25 23:25  Addr Edit/Del Reply

    미안
    정줄놓고 포스팅했더니 길이가 너무 기네 -_-;

  2. -1 < x <1 일때
    루트(1+x) = 1 + 1/2*x - 1/(2^2*2!)*x^2 + 3/(2^3*3!)*x^3 - (3*5)/(2^4*4!)*x^4 + (3*5*7)/(2^5*5!)*x^5 - ........
    이 식이 만족한다고 하네요 ㅇㅅㅇ 나름 기대하고있슙니다.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.26 00:21  Addr Edit/Del

      아.. 테일러다항식 말인가요?

      이 방법으로도 제곱근을 충분히 구할 수 있지만;

      글의 성격과 미묘하게 빗나가는데다
      테일러다항식을 설명하기 위해서는 고등학교 수학지식이 필요해서..;

      나중에 기회가 되면 다루도록 하지요//

  3. 뉴턴의 방법(Newton's way)랑 같은건감?

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.26 01:14  Addr Edit/Del

      아냐; 뉴턴메소드랑도 조금 달라;

      Bisection은 미분이 필요 없으니까;


      뉴턴메소드도 잊고 있었는데 이걸로도 구할 수 있겠군 ㅋㅋ
      (하지만 계획에 없던거라 아마 포스팅은 안할듯)

  4. 미분이 필요 없다라... 꽤 괜찮은데?-_-?

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.27 01:46  Addr Edit/Del

      그 대신
      찾고자 하는 값이 어느 구간 안에 들어있는지정도는 알아야함;

      이 글에 올린 함수는 내부에서 구간을 설정하고 있지만

      소스를 개량하면 사용자가 구간을 정해줄 수도 있겠지//

  5. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.27 01:44  Addr Edit/Del Reply

    [27일 am 1:44] squareRoot 함수의 body를 조금 수정했습니다

부제 : 말이나 못하면 밉지나 않지. (?)



자, 이번에는
"Round 1"에서의 피보나치 수열을 나름 "개량된" 재귀함수로 구현해보도록 하겠습니다


(동적 할당을 new가 아닌 calloc으로 하는 것에는 그닥 신경쓰지 말고 -_-;)

다른 점이 눈에 보이십니까?


Fn에서의 n 외에 배열을(엄밀히 말하면 포인터지만) input으로 하나 더 받고 있는데

이놈이 하는 역할이 뭔고 하니

배열에서의 n번째 위치에 저장된 값(Fn)이 0이면 Fn-1과 Fn-2의 합을 Fn에 저장한 뒤 리턴하고,
0이 아니면 즉시 그 값을 리턴하도록 Fn을 기록해두는 역할을 하고 있습니다

n = 5
impR(5) 호출
fSeq[5] 검사, fSeq[5]의 값이 0인가?
True ⇒ fSeq[5] = impR(4) + impR(3) 시행

 impR(4) 호출
 fSeq[4] 검사, fSeq[4]의 값이 0인가?
 True ⇒ fSeq[4] = impR(3) + impR(2) 시행

  impR(3) 호출
  fSeq[3] 검사, fSeq[3]의 값이 0인가?
  True ⇒ fSeq[3] = impR(2) + impR(1) 시행

   impR(2) 호출
   fSeq[2] 검사, fSeq[2]의 값이 0인가?
   True ⇒ n ≤ 2 이므로 fSeq[2] = 1 시행 후 fSeq[2] 리턴

   impR(1) 호출
   fSeq[1] 검사, fSeq[1]의 값이 0인가?
   True ⇒ n ≤ 2 이므로 fSeq[1] = 1 시행 후 fSeq[1] 리턴

  시행결과 : fSeq[3] = 2

  impR(2) 호출
  fSeq[2] 검사, fSeq[2]의 값이 0인가?
  False ⇒ fSeq[2] 리턴

 시행결과 : fSeq[4] = 3

 impR(3) 호출
 fSeq[3] 검사, fSeq[3]의 값이 0인가?
 False ⇒ fSeq[3] 리턴

시행결과 : fSeq[5] = 5

fSeq[5] 리턴

설명은 이정도로 하고, 실행시간을 재보도록 할까요?


사용자 삽입 이미지

예전의 재귀보다 훨씬 빠르죠?

개인적으로는 거의 반복과 비슷한 수준에 이르렀다고 생각합니다

그러나, 위에서도 볼 수 있듯이

input이 40000을 찍는 순간, 우리의 컴퓨터는 함수를 호출할 메모리가 부족하여 재귀를 멈춰버리고 맙니다
(실제로 40000까지 안전한건 아니고, 저희 집의 경우 12000정도만 찍어도 재귀가 멈춰버리는 듯 하더군요)


그리하여, 속도는 비슷한 듯 하지만 메모리상의 문제에서 재귀가 패배하게 됩니다



여태까지 언급했던 것들 외에 재귀가 반복보다 빠른 케이스를 지난 주에 한가지 언급해드렸습니다

바로 멱(거듭제곱)을 구하는 것입니다

이건 따로 시간을 잰다거나 하지 않고 간단히 소스만 보고 넘어가도록 하죠





R은 재귀, I는 반복입니다

반복의 경우 시간복잡도가 O(n)이지만 재귀의 경우는 시간복잡도가 O(log_2 n)정도밖에 되지 않습니다

그래서 이 경우에는 재귀가 반복보다 "훨씬" 빠르겠습니다





피보나치 수열에 대해 얘기를 하다가 "재귀vs.반복"으로 빠져버렸습니다만

굳이 결론을 내리자면 "상황에 따라 더 적절한 것을 사용하는" 것이 괜찮을 거라 생각합니다

다음번에는 다른 주제를 얘기해보도록 하겠습니다~



여담이지만,
피보나치수열의 값을 구하는 데 있어서 수학함수를 사용하면 반복보다 훨씬 더 빠르게 되는 식이 있습니다 :D

(포스팅 소요시간 : 약 70분)
posted by Milkskin

댓글을 달아 주세요

부제 : 컴퓨터조차 세상의 끝을 보기가 쉽지 않아.

하노이 탑

19세기경 유럽에서는 "창세기부터 지금까지 브라마 사원에서 계속되고 있다"는 선전용 문구와 함께 유명했던 "하노이 탑"이라는 게임이 있었다.

전설에 의하면 아직도 계속되고 있다는 이 게임은 창세기에 그 사원의 사제가 하나님으로부터 다이아몬드로 된 세 개의 말뚝에 꽂혀 있는 구리 제단을 받았는데, 첫 번째 말뚝에는 금으로 된 64개의 원반이 쌓여 있었고, 각 원반은 바로 밑에 있는 원반보다 조금씩 작았다. 사제는 모든 원반을 두 번째 말뚝을 이용하여 세 번째 말뚝에 옮기는 임무를 부여 받았는데, 다음과 같은 규칙이 있었다.

1. 원반은 한번에 하나씩만 옮겨야 한다. 결국 가장 작은 맨 위의 원반만 옮길 수 있다.
2. 위에 놓인 원반은 아래의 원반보다 클 수 없다.

만일 그 사제가 64개의 원반을 옮기는 작업을 다 끝내면, 이 세상에는 종말이 온다고 한다.
(위 내용은 'C로 배우는 프로그래밍 기초'에서 일부 발췌했음을 알려드립니다)


지난 주에
재귀가 반복보다 더 나은 경우를 찾아오겠다고 대뜸 선언해버리고
찾아도 찾아도 안나오길래 한 며칠간 머리좀 싸맸지요

그러다 이것(하노이)과 멱(거듭제곱)을 구하는 케이스를 찾아내었는데
아무래도 이걸 올리는게 좋을 것 같다는 생각을 했습니다

피보나치 수열과 더불어 프로그래밍을 배우는 사람이라면 한번은 보고 지나가게 되는 내용입니다

재귀로 구현한 것과 같은 알고리즘을 사용하기가 다소 난해하여
반복으로 구현한 것을 자주 볼 일은 없겠지만 이것도 반복으로 구현이 가능합니다

먼저 재귀부터 보시죠



역시 재귀가 알고리즘 자체는 매우 간단하지 않습니까?

간단히 설명을 하자면
원반이 1개일 때는 시작 축에서 끝 축으로 옮기기만 하면 됩니다

원반의 개수가 n개가 되면
일단 n-1개의 원반을 시작 축에서 중간 축으로 몰아놓고,
n번째 원반을 끝 축으로 옮긴 뒤 남은 n-1개의 원반을 끝 축으로 옮기면 되겠죠

이번에도 input에 따른 실행시간을 보겠습니다

사용자 삽입 이미지

input n에 대해서 2^n -1번의 시행을 출력하기 때문에
input의 증가에 따른 시간의 증가가 눈에 띄게 증가함을 알 수 있습니다

반복으로 구현한 것을 보시죠



ㅋㅋㅋㅋㅋㅋㅋㅋ 조금 복잡하죠?

이 알고리즘에 대해 간단히(?) 설명을 하자면.. 아래의 컬러박스를 보시면 됩니다
컬러박스 하단에 설명을 해놓았으나, 이해가 안되시면
컬러박스 상단에 써놓은 진행을 보고 대충 이렇게 되는구나 하고 넘어가시면 됩니다

n = 3
0: 123 x x (시작)
1: 23 x 1  (원반1 이동)
2: 3 2 1    (원반2 이동)
3: 3 12 x  (원반1 이동)
4: x 12 3  (원반3 이동)
5: 1 2 3    (원반1 이동)
6: 1 x 23  (원반2 이동)
7: x x 123 (원반1 이동, 끝)
--------
n = 4
 0: 1234 x x (시작)
 1: 234 1 x  (원반1 이동)
 2: 34 1 2    (원반2 이동)
 3: 34 x 12   (원반1 이동)
 4: 4 3 12    (원반3 이동)
 5: 14 3 2    (원반1 이동)
 6: 14 23 x   (원반2 이동)
 7: 4 123 x   (원반1 이동)
 8: x 123 4   (원반4 이동)
 9: x 23 14   (원반1 이동)
10: 2 3 14    (원반2 이동)
11: 12 3 4    (원반1 이동)
12: 12 x 34  (원반3 이동)
13: 2 1 34    (원반1 이동)
14: x 1 234  (원반2 이동)
15: x x 1234 (원반1 이동, 끝)
--------
두 경우를 각각 보시면
원반1은 시행수를 2로 나눈 나머지가 1일 때 이동하고,
원반2는 시행수를 4로 나눈 나머지가 2일 때 이동하고,
원반3은 시행수를 8로 나눈 나머지가 4일 때 이동하고
모든 원반이 이것을 만족하므로 for문을 중첩시켜서 돌리면 적당하겠지요

이동경로의 경우
n이 홀수이면
 홀수번의 원반은 '시작 축 → 끝 축 → 중간 축 → 시작 축'을 반복하고,
 짝수번의 원반은 '시작 축 → 중간 축 → 끝 축 → 시작 축'을 반복합니다
n이 짝수이면
 홀수번의 원반은 '시작 축 → 중간 축 → 끝 축 → 시작 축'을 반복하고,
 짝수번의 원반은 '시작 축 → 끝 축 → 중간 축 → 시작 축'을 반복합니다
모든 원반이 이것을 만족하고, 이동경로의 경우 3회마다 반복되므로
원반1을 예로 들면
 '시행수를 6(=3×2)으로 나눈 나머지'를 2로 나눈 몫이 0이면 1회째 이동을 하고,
 '시행수를 6(=3×2)으로 나눈 나머지'를 2로 나눈 몫이 1이면 2회째 이동을 하고,
 '시행수를 6(=3×2)으로 나눈 나머지'를 2로 나눈 몫이 2이면 3회째 이동을 합니다
나머지가 0인 경우를 skip하기 위해 if문을 중첩하고, 3회의 이동을 처리하기 위해 switch를 사용하였습니다

피보나치 때는 반복이 더 빠를 것 같다는 것을 비교적 쉽게 짐작할 수 있었는데 이건 잘 모르겠죠?
별 수 없이 프로그램을 돌려서 시간을 재는 수 밖에는 없을 것 같네요

사용자 삽입 이미지

.. 미세하지만 재귀가 빠르군요;

사실 이건 한두번 돌리고 찍은 스샷들이라 오차가 있을 수 있으며
실제 실행시 반복으로 구현한 쪽이 조금 더 빠르게 나올 수 도 있습니다

.. 만,

이걸 한번 보시겠습니까?


사용자 삽입 이미지
사용자 삽입 이미지

!?

위의 두 스샷과는 비교도 안될만큼 빠르지 않습니까?
input을 입력하고 실행창을 작업표시줄로 내려버리면 나타나는 결과인데.. 원인을 전혀 모르겠습니다?
(혹시나 해서 피보나치에도 해봤는데 거기엔 안되더군요 -_-;)

원인을 아시는 분은 담당파트와 관계없이 포스팅좀.. 굽신굽신


마지막 스샷까지 참고하면 이번엔 명백한 재귀의 승리인가요 ㅋ

다음번에는
지난 주의 피보나치에서 실행속도가 너무 느리던 재귀함수를 개량해보도록 하겠습니다 (__)

(포스팅 소요시간 : 약 150분)
posted by Milkskin

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.12 00:52  Addr Edit/Del Reply

    .. 아 스압 좀 쩌네 -_-;

  2. 재귀가 더 빠르게 나온 이유 첫번째. if문의 비율. 알고리즘의 시간복잡도는 둘다 O(2^n)꼴로 같지만 if문은 좀 심히 느림. 재귀호출에서는 if문 비교가 1회뿐이나, 반복의 경우는 for문 내부의 체크와 함께 switch문까지도 존재해 더 느릴 수 밖에 없음.

  3. 재귀가 더 빠르게 나온 이유 두번째. 연산자.... 나누기와 나머지, 곱하기, pow는 좀.... 심각하게 느림 -_-; 그게 수도없이 반복되니 그 비율이 적은 재귀가 압도적으로 빠를 수 밖에...

  4. 그리고 마지막.... 작업표시줄로 내려 버렸을 때 일어나는 저 현상은... OS의 멀티태스킹에서 일어나는 문제. 코어를 병렬로 여러개 나열한 듀얼코어나 쿼드코어 등에서 더 확연하게 나타날 수 있음. 자세한 내용은 나중에 포스팅으로 띄우겠음.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.12 01:17  Addr Edit/Del

      아.. 멀티태스킹.. 짐작은 했는데 그게 맞군? -_-;

부제 : 그대, 피보나치 수열이라고 들어보았는가?

Fibonacci Numbers

Consider the following sequence of numbers, which begins with two 1's and where each successive term is equal to the sum of the preceding pair of terms. These numbers, called Fibonacci numbers, are arranged in the Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... .

If F1 = 1, F2 = 1, F3 = 2, F4 = 3, and so on, then this sequence can be written recursively as

Fn+2 = Fn+1 + Fn    for all nN, where F1 = F2 = 1.
(위 내용은 A Friendly Introduction to ANALYSIS 2/e에서 일부 발췌했음을 알려드립니다)


피보나치 수열이란, 첫째 항과 둘째 항이 모두 1이고 그 뒤로는 직전의 두 항의 합으로 이루어진 수열입니다
(쓰는 곳에 따라 0번째(F0) 항을 0으로, 1번째(F1) 항을 1로 놓고 얘기하기도 하지만, 여기서는 1, 1, 2, …인 형태로 얘기합니다)

수열 자체의 알고리즘이 매우 간단하여 프로그래밍을 배우는 사람이라면 꼭 한번은 보고 지나가게 되는 내용입니다

이것의 구현 방법은 재귀(Recursion)와 반복(Iteration)이 있습니다, 먼저 재귀부터 보시죠




간단하죠? 함수 자체가 위의 점화식의 모양대로 호출이 됩니다
허나 이것의 경우 단점이 있는데,

재귀로 자기 자신을 2번이나 호출하기 때문에 처음의 input이 크면 클 수록 호출회수가 많아져서 그만큼 시간이 오래 걸린다는 것,
또 하나는 함수를 계속 호출하는 것이기 때문에 함수를 위한 메모리가 부족하면 원하는 결과를 얻을 수 없다는 것입니다

메모리에 대해서는 잘 모르니 저정도만 언급하기로 하고,
input이 적당히 커지면 실행시간이 얼마나 오래걸리는지 보도록 하죠

사용자 삽입 이미지

F40을 재귀로 구하는 프로그램입니다
10회 실행 후 평균을 재었더니 9.3156초가 나왔습니다

반복시의 결과는 아래에서 보기로 하죠




함수의 body부분이 위의 점화식만큼 간단하지는 않습니다
비교를 용이하게 하기 위해 base case는 재귀와 같게 하였습니다

n이 3 이상일 때 if문 내의 for문이 작동하는데
int형 변수의 선언이 있긴 하지만 재귀 때와 달리 메모리의 소비가 그리 크진 않을 것 같습니다

그리고 함수의 추가 호출도 없이 for문 내에서 모든 것을 해결하고 있으니
짐작하시기에도 이게 더 빠를 것 같다는 느낌이 들지 않나요?

확인해봅시다

사용자 삽입 이미지

보이십니까? 이 차이가;

재귀 때의 40과 비교하기 위해 일부러 4×10ⁿ 형태의 것들만 입력해봤는데
심지어 4억번째 값을 구하기 위해 함수호출을 하여도 재귀 때의 40번째 값을 구하기 위한 것보다 약 3배정도 빠르죠 (2.656초;)


일반적인 경우, 재귀와 반복이 비슷한 수준일 것으로 추측되나
피보나치에서는 재귀의 명백한 패배입니다 ㅠ

다음번에는 재귀가 반복보다 더 나은 경우를 가지고 찾아오겠습니다 (__)

(포스팅 소요시간 : 약 80분)
posted by Milkskin

댓글을 달아 주세요

  1. 재귀와 반복은 당연히 반복의 압승. 다음번 내 포스트 쓸 때 내가 왜 그런지에 대해 쓰겠음. 클클클. 글거리 줘서 캄사.

    • Favicon of http://zfanta.com BlogIcon  환타 2008.09.05 00:09  Addr Edit/Del

      재귀놀이 새치기 하고싶지만 ㅎㅎ
      dlbo님의 포스팅이 보고싶어서 기다리렵니다 ㅎㅎ

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.09.05 02:03  Addr Edit/Del

      괜찮아요 ㅋㅋㅋㅋ 다음주 다같이 재귀스페셜 가봐요 ㅋㅋㅋㅋㅋㅋㅋ

  2. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.04 22:14  Addr Edit/Del Reply

    흠. 흥미롭군 ㅇ_ㅇ

    재귀호출보다 반복 제어문으로 처리하는것이 빠른 경우가 대다순데.

    난 일반적으로 재귀호출로 첫번째 코드 짠 뒤에 반복문으로 옵티마이즈 하는편이라. -_-a

    다음주엔 과연 어떤 것을 보여줄 건지... 기대되는구만.ㅋㅋ

    근데... 이젠 내 차례인가 ㄱ-

    일주일 무지하게 빨리 가는군.

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.09.04 22:02  Addr Edit/Del

      재귀가 느리대잖어 ㅋㅋㅋ 나도 거꾸로 쓸 뻔 했다.

    • Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.04 22:06  Addr Edit/Del

      담번엔 재귀가 반복보다 나은 경우를 알려주겠다지 않소. -_-;

      난 그게 흥미롭단게지

안녕하세요 Mr.K입니다//

수학과 소속이고,
프로그래밍을 배우는 것도 이제 곧 3학기째에 들어갑니다만

어쩌다보니 스카웃되어 이렇게 팀블로그의 초석을 다지는 데 한몫 하게 되었습니다

제가 앞으로 포스팅 할 분야는
딱히 어느것이다- 라고 말하긴 그렇고,

수학적으로 정의되어있는 것을 프로그래밍으로 구현해본다거나

'무한'의 범주에 들어있는 것들을 어느정도 끌어내려서 '유한'하게 구현해본다거나

기타 등등,
책을 찾아보고 프로그래밍과 연관시킬 수 있는 것이라 생각되면 전부 시도해볼 생각입니다



그리고 PKU나 UVa에 대해 미리 얘기를 해두자면..

저같은 경우 '얼마나 빠른가'는 제쳐두고 '얼마나 정확한가'에 신경을 쓰는 편이기 때문에
문제에서 요구하는 답을 내는 것에 집중할 생각입니다

그때문에 전체적인 코드의 형태가 다를 수 있음은 물론이고,
코드 자체의 길이도 다소 길어질 수도 있습니다

아마 그래서 당연한 얘기일지도 모르지만,
온라인에 제출했을 때 accept되지 않을 가능성도 높을 듯 하니 이해해주시기 바랍니다



그럼 앞으로 열심히 해보아요//

posted by Milkskin

댓글을 달아 주세요

  1. 컴공보다 플밍잘하는 Mr.곽 ㅁ_ㅁ

prev 1 next