ar回歸演算法
Ⅰ 線性回歸方程定義和演算法是怎麼樣的
且為觀測值的樣本方差.
線性方程稱為關於的線性回歸方程,稱為回歸系數,對應的直線稱為回歸直線.順便指出,將來還需用到,其中為觀測值的樣本方差.
利用公式求解：b=
a=y（平均數）-b*（平均數）
線性同餘方程
在數論中，線性同餘方程是最基本的同餘方程，「線性」表示方程的未知數次數是一次，即形如：
的方程。此方程有解當且僅當 b 能夠被 a 與 n 的最大公約數整除（記作 gcd(a,n) | b）。這時，如果 x0 是方程的一個解，那麼所有的解可以表示為：
其中 d 是a 與 n 的最大公約數。在模 n 的完全剩餘系 {0,1,…,n-1} 中，恰有 d 個解。
目錄
1 例子
2 求特殊解
3 線性同餘方程組
4 參見
例子
在方程
3x ≡ 2 (mod 6)
中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程無解。
在方程
5x ≡ 2 (mod 6)
中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一個解: x=4。
在方程
4x ≡ 2 (mod 6)
中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有兩個解: x=2 and x=5。
求特殊解
對於線性同餘方程
ax ≡ b (mod n) (1)
若 d = gcd(a, n 整除 b ，那麼為整數。由裴蜀定理，存在整數對 (r,s) （可用輾轉相除法求得）使得 ar+sn=d，因此 是方程 (1) 的一個解。其他的解都關於與 x 同餘。
舉例來說，方程
12x ≡ 20 (mod 28)
中 d = gcd(12,28) = 4 。注意到 ，因此 是一個解。對模 28 來說，所有的解就是 {4,11,18,25} 。
線性同餘方程組
線性同餘方程組的求解可以分解為求若干個線性同餘方程。比如，對於線性同餘方程組：
2x ≡ 2 (mod 6)
3x ≡ 2 (mod 7)
2x ≡ 4 (mod 8)
首先求解第一個方程，得到x ≡ 1 (mod 3)，於是令x = 3k + 1，第二個方程就變為：
9k ≡ �6�11 (mod 7)
解得k ≡ 3 (mod 7)。於是，再令k = 7l + 3，第三個方程就可以化為：
42l ≡ �6�116 (mod 8)
解出：l ≡ 0 (mod 4)，即 l = 4m。代入原來的表達式就有 x = 21(4m) + 10 = 84m + 10，即解為：
x ≡ 10 (mod 84)
對於一般情況下是否有解，以及解得情況，則需用到數論中的中國剩餘定理。
參見
二次剩餘
中國剩餘定理
談談解線性同餘方程
因為ACM/ICPC中有些題目是關於數論的，特別是解線性同餘方程，所以有必要准備下這方面的知識。關於這部分知識，我先後翻看過很多資料，包括陳景潤的《初等數論》、程序設計競賽例題解、「黑書」和很多網上資料，個人認為講的最好最透徹的是《演算法導論》中的有關章節，看了之後恍然大悟。經過幾天的自學，自己覺得基本掌握了其中的「奧妙」。拿出來寫成文章。
那麼什麼是線性同餘方程？對於方程：ax≡b(mod m)，a，b，m都是整數，求解x 的值。
解題常式：pku1061 青蛙的約會 解題報告
符號說明：
mod表示：取模運算
ax≡b(mod m)表示：(ax - b) mod m = 0，即同餘
gcd(a,b)表示：a和b的最大公約數
求解ax≡b(mod n)的原理：
對於方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整數。而ax≡b(mod n)的解可以由x，y來堆砌。具體做法，見下面的MLES演算法。
第一個問題：求解gcd(a,b)
定理一：gcd(a,b) = gcd(b,a mod b)
實現：古老的歐幾里德演算法
int Euclid(int a,int b)
{
if(b == 0)
return a;
else
return Euclid(b,mod(a,b));
}
附：取模運算
int mod(int a,int b)
{
if(a >= 0)
return a % b;
else
return a % b + b;
}
第二個問題：求解ax + by = gcd(a,b)
定理二：gcd(b,a mod b) = b * x' + (a mod b) * y'
= b * x' + (a - a / b * b) * y'
= a * y' + b * (x' - a / b * y')
= a * x + b * y
則：x = y'
y = x' - a / b * y'
實現：
triple Extended_Euclid(int a,int b)
{
triple result;
if(b == 0)
{
result.d = a;
result.x = 1;
result.y = 0;
}
else
{
triple ee = Extended_Euclid(b,mod(a,b));
result.d = ee.d;
result.x = ee.y;
result.y = ee.x - (a/b)*ee.y;
}
return result;
}
附：三元組triple的定義
struct triple
{
int d,x,y;
};
第三個問題：求解ax≡b(mod n)
實現：由x，y堆砌方程的解
int MLES(int a,int b,int n)
{
triple ee = Extended_Euclid(a,n);
if(mod(b,ee.d) == 0)
return mod((ee.x * (b / ee.d)),n / ee.d);
else
return -1;
}//返回-1為無解，否則返回的是方程的最小解
說明：ax≡b(mod n)解的個數：
如果ee.d 整除 b 則有ee.d個解；
如果ee.d 不能整除 b 則無解。