선형 방정식 풀기
-
08-06-2019 - |
문제
C, Objective C 또는 (필요한 경우) C++에서 선형 방정식 시스템을 프로그래밍 방식으로 풀어야 합니다.
다음은 방정식의 예입니다.
-44.3940 = a * 50.0 + b * 37.0 + tx
-45.3049 = a * 43.0 + b * 39.0 + tx
-44.9594 = a * 52.0 + b * 41.0 + tx
이것으로부터 나는 다음에 대한 최선의 근사치를 얻고 싶습니다. a
, b
, 그리고 tx
.
다른 팁
손으로 문제를 푸는 것과 똑같은 방식으로 프로그램을 사용하여 이 문제를 풀 수 있습니다(곱셈과 뺄셈을 한 다음 결과를 방정식에 다시 입력).이것은 매우 표준적인 중등학교 수준의 수학입니다.
-44.3940 = 50a + 37b + c (A)
-45.3049 = 43a + 39b + c (B)
-44.9594 = 52a + 41b + c (C)
(A-B): 0.9109 = 7a - 2b (D)
(B-C): 0.3455 = -9a - 2b (E)
(D-E): 1.2564 = 16a (F)
(F/16): a = 0.078525 (G)
Feed G into D:
0.9109 = 7a - 2b
=> 0.9109 = 0.549675 - 2b (substitute a)
=> 0.361225 = -2b (subtract 0.549675 from both sides)
=> -0.1806125 = b (divide both sides by -2) (H)
Feed H/G into A:
-44.3940 = 50a + 37b + c
=> -44.3940 = 3.92625 - 6.6826625 + c (substitute a/b)
=> -41.6375875 = c (subtract 3.92625 - 6.6826625 from both sides)
그래서 당신은 끝납니다 :
a = 0.0785250
b = -0.1806125
c = -41.6375875
이 값을 다시 A, B, C에 연결하면 올바른 값임을 알 수 있습니다.
비결은 간단한 4x3 행렬을 사용하여 3x2 행렬로 변환한 다음 "a = n"인 2x1을 사용하는 것입니다. n은 실제 숫자입니다.일단 그것을 갖고 나면 이를 다음 행렬에 공급하여 다른 값을 얻은 다음 모든 변수를 풀 때까지 이 두 값을 다음 행렬에 넣습니다.
N개의 서로 다른 방정식이 있는 경우 항상 N개의 변수를 풀 수 있습니다.나는 이 두 가지가 다르기 때문에 구별된다고 말합니다.
7a + 2b = 50
14a + 4b = 100
그들은 같은 방정식에 2를 곱하면 답을 얻을 수 없습니다. 첫 번째 방정식에 2를 곱하고 빼면 사실이지만 쓸모없는 진술이 남습니다.
0 = 0 + 0
예를 들어, 질문에 있는 연립방정식을 계산하는 C 코드는 다음과 같습니다.먼저 몇 가지 필요한 유형, 변수, 방정식을 인쇄하기 위한 지원 함수 및 시작 main
:
#include <stdio.h>
typedef struct { double r, a, b, c; } tEquation;
tEquation equ1[] = {
{ -44.3940, 50, 37, 1 }, // -44.3940 = 50a + 37b + c (A)
{ -45.3049, 43, 39, 1 }, // -45.3049 = 43a + 39b + c (B)
{ -44.9594, 52, 41, 1 }, // -44.9594 = 52a + 41b + c (C)
};
tEquation equ2[2], equ3[1];
static void dumpEqu (char *desc, tEquation *e, char *post) {
printf ("%10s: %12.8lf = %12.8lfa + %12.8lfb + %12.8lfc (%s)\n",
desc, e->r, e->a, e->b, e->c, post);
}
int main (void) {
double a, b, c;
다음으로, 3개의 미지수가 있는 3개의 방정식을 2개의 미지수가 있는 2개의 방정식으로 축소합니다.
// First step, populate equ2 based on removing c from equ.
dumpEqu (">", &(equ1[0]), "A");
dumpEqu (">", &(equ1[1]), "B");
dumpEqu (">", &(equ1[2]), "C");
puts ("");
// A - B
equ2[0].r = equ1[0].r * equ1[1].c - equ1[1].r * equ1[0].c;
equ2[0].a = equ1[0].a * equ1[1].c - equ1[1].a * equ1[0].c;
equ2[0].b = equ1[0].b * equ1[1].c - equ1[1].b * equ1[0].c;
equ2[0].c = 0;
// B - C
equ2[1].r = equ1[1].r * equ1[2].c - equ1[2].r * equ1[1].c;
equ2[1].a = equ1[1].a * equ1[2].c - equ1[2].a * equ1[1].c;
equ2[1].b = equ1[1].b * equ1[2].c - equ1[2].b * equ1[1].c;
equ2[1].c = 0;
dumpEqu ("A-B", &(equ2[0]), "D");
dumpEqu ("B-C", &(equ2[1]), "E");
puts ("");
다음으로, 두 개의 미지수가 있는 두 방정식을 하나의 미지수가 있는 하나의 방정식으로 축소합니다.
// Next step, populate equ3 based on removing b from equ2.
// D - E
equ3[0].r = equ2[0].r * equ2[1].b - equ2[1].r * equ2[0].b;
equ3[0].a = equ2[0].a * equ2[1].b - equ2[1].a * equ2[0].b;
equ3[0].b = 0;
equ3[0].c = 0;
dumpEqu ("D-E", &(equ3[0]), "F");
puts ("");
이제 우리는 다음과 같은 유형의 공식을 갖게 되었습니다. number1 = unknown * number2
, 우리는 다음을 사용하여 알 수 없는 값을 간단하게 계산할 수 있습니다. unknown <- number1 / number2
.그런 다음 해당 값을 파악한 후 이를 두 개의 미지수가 있는 방정식 중 하나로 대체하고 두 번째 값을 계산합니다.그런 다음 (현재 알려진) 두 가지 미지수를 원래 방정식 중 하나로 대체하면 이제 세 가지 미지수 모두에 대한 값을 갖게 됩니다.
// Finally, substitute values back into equations.
a = equ3[0].r / equ3[0].a;
printf ("From (F ), a = %12.8lf (G)\n", a);
b = (equ2[0].r - equ2[0].a * a) / equ2[0].b;
printf ("From (D,G ), b = %12.8lf (H)\n", b);
c = (equ1[0].r - equ1[0].a * a - equ1[0].b * b) / equ1[0].c;
printf ("From (A,G,H), c = %12.8lf (I)\n", c);
return 0;
}
해당 코드의 출력은 이 답변의 이전 계산과 일치합니다.
>: -44.39400000 = 50.00000000a + 37.00000000b + 1.00000000c (A)
>: -45.30490000 = 43.00000000a + 39.00000000b + 1.00000000c (B)
>: -44.95940000 = 52.00000000a + 41.00000000b + 1.00000000c (C)
A-B: 0.91090000 = 7.00000000a + -2.00000000b + 0.00000000c (D)
B-C: -0.34550000 = -9.00000000a + -2.00000000b + 0.00000000c (E)
D-E: -2.51280000 = -32.00000000a + 0.00000000b + 0.00000000c (F)
From (F ), a = 0.07852500 (G)
From (D,G ), b = -0.18061250 (H)
From (A,G,H), c = -41.63758750 (I)
3x3 선형 방정식 시스템의 경우 자신만의 알고리즘을 출시해도 괜찮을 것 같습니다.
그러나 정확성, 0으로 나누기 또는 매우 작은 숫자, 무한히 많은 솔루션에 대해 무엇을 해야할지 걱정해야 할 수도 있습니다.내 제안은 다음과 같은 표준 수치 선형 대수 패키지를 사용하는 것입니다. 라팩.
다음을 살펴보세요. 마이크로소프트 솔버 재단.
이를 사용하면 다음과 같은 코드를 작성할 수 있습니다.
SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();
Decision a = new Decision(Domain.Real, "a");
Decision b = new Decision(Domain.Real, "b");
Decision c = new Decision(Domain.Real, "c");
model.AddDecisions(a,b,c);
model.AddConstraint("eqA", -44.3940 == 50*a + 37*b + c);
model.AddConstraint("eqB", -45.3049 == 43*a + 39*b + c);
model.AddConstraint("eqC", -44.9594 == 52*a + 41*b + c);
Solution solution = context.Solve();
string results = solution.GetReport().ToString();
Console.WriteLine(results);
출력은 다음과 같습니다.
===솔버 파운데이션 서비스 보고서===
날짜 시간:2009년 4월 20일 23:29:55
모델명:기본
요청된 기능:LP
해결 시간(ms):1027
총 시간(밀리초):1414
해결 완료 상태:최적
선택한 솔버:Microsoft.SolverFoundation.Solvers.SimplexSolver
지시어:
Microsoft.SolverFoundation.Services.Directive
연산:원시
산수:잡종
가격(정확한):기본
가격(이중):가장 가파른 가장자리
기초:느슨하게
피벗 수:삼
===솔루션 세부정보===
목표:
결정:
ㅏ:0.0785250000000004
비:-0.180612500000001
씨:-41.6375875
작업을 수행하거나 실제로 매트릭스 작업 등을 수행하고 각 단계를 수행하는 소프트웨어 패키지를 찾고 계십니까?
첫 번째는 내 동료가 방금 사용한 것입니다. 오캠 GLPK.그것은 단지 포장지일 뿐입니다. GLPK, 하지만 설정에 필요한 많은 단계가 제거됩니다.하지만 C에서는 GLPK를 고수해야 할 것 같습니다.후자의 경우 예전에 LP를 배울 때 썼던 오래된 글을 저장해 준 Delicious 덕분에, PDF.추가로 설정하는 데 구체적인 도움이 필요한 경우 알려주시면 저나 누군가가 다시 돌아와서 도와줄 것이라고 확신합니다. 하지만 여기에서는 꽤 간단하다고 생각합니다.행운을 빌어요!
질문의 표현으로 볼 때 미지수보다 방정식이 더 많고 불일치를 최소화하려는 것 같습니다.이는 일반적으로 불일치의 제곱합을 최소화하는 선형 회귀를 통해 수행됩니다.데이터 크기에 따라 스프레드시트나 통계 패키지에서 이 작업을 수행할 수 있습니다.R은 무엇보다도 선형 회귀를 수행하는 고품질 무료 패키지입니다.선형 회귀에는 할 일이 많지만 (그리고 많은 문제가 있습니다) 간단한 경우에는 간단합니다.다음은 데이터를 사용하는 R 예시입니다."tx"는 모델에 대한 절편입니다.
> y <- c(-44.394, -45.3049, -44.9594)
> a <- c(50.0, 43.0, 52.0)
> b <- c(37.0, 39.0, 41.0)
> regression = lm(y ~ a + b)
> regression
Call:
lm(formula = y ~ a + b)
Coefficients:
(Intercept) a b
-41.63759 0.07852 -0.18061
런타임 효율성 측면에서 다른 사람들이 나보다 더 나은 대답을 했습니다.항상 변수와 같은 수의 방정식을 갖게 된다면, 나는 다음을 좋아합니다. 크레이머의 법칙 구현하기 쉽기 때문이죠.행렬의 행렬식을 계산하는 함수를 작성하고(또는 이미 작성된 것을 사용하면 거기에서 찾을 수 있을 것이라고 확신합니다) 두 행렬의 행렬식을 나눕니다.
개인적으로 나는 알고리즘에 부분적입니다. 수치적 레시피.(저는 C++ 버전을 좋아합니다.)
이 책은 알고리즘이 작동하는 이유를 알려주고 해당 알고리즘의 꽤 잘 디버깅된 구현을 보여줍니다.
물론 맹목적으로 사용할 수도 있습니다. 클랩팩 (나는 그것을 성공적으로 사용했습니다.) 그러나 적어도 이러한 알고리즘을 안정적으로 만드는 데 들어간 작업 종류에 대한 희미한 아이디어를 갖기 위해 먼저 가우스 제거 알고리즘을 직접 입력하겠습니다.
나중에 좀 더 흥미로운 선형 대수학을 하고 있다면, 소스 코드를 둘러보세요. 옥타브 많은 질문에 답할 것입니다.
function x = LinSolve(A,y)
%
% Recursive Solution of Linear System Ax=y
% matlab equivalent: x = A\y
% x = n x 1
% A = n x n
% y = n x 1
% Uses stack space extensively. Not efficient.
% C allows recursion, so convert it into C.
% ----------------------------------------------
n=length(y);
x=zeros(n,1);
if(n>1)
x(1:n-1,1) = LinSolve( A(1:n-1,1:n-1) - (A(1:n-1,n)*A(n,1:n-1))./A(n,n) , ...
y(1:n-1,1) - A(1:n-1,n).*(y(n,1)/A(n,n)));
x(n,1) = (y(n,1) - A(n,1:n-1)*x(1:n-1,1))./A(n,n);
else
x = y(1,1) / A(1,1);
end