Source code for finding an orthonormal basis with the Gram-Schmidt orthogonalization method

I have implemented the source code to create an orthonormal basis using the Gram-Schmidt orthogonalization method, so I will share it. (Dimension is fixed at 3)

Referenced site

Meaning and concrete examples of Gram-Schmidt orthogonalization method http://mathtrain.jp/gramschmidt

Gram-Schmidt orthonormalization method http://li.nu/blog/2010/07/gram-schmidt.html

Source code (Java)

package hoge.piyo;

import javax.vecmath.Vector3d;

public class LinearAlgebraUtil {
	
	/**
	 *Vector a1, a2,Create an orthonormal basis for a3.
	 * a1, a2,a3 must be first-order independent.
	 ** Argument check omitted
	 * @param a1 vector a1
	 * @param a2 vector a2
	 * @param a3 vector a3
	 * @return Orthonormal basis u1, u2,Vector3d array stored in u3 order
	 */
	public static Vector3d[] createOrthonormalBasis(
			Vector3d a1, Vector3d a2, Vector3d a3) {
		
		// u1
		Vector3d u1 = createNormalizedVector(a1);
		
		// u2
		Vector3d v2 = new Vector3d(a2);
		//Excludes components in the u1 direction from v2.
		removeOrthogonalProjectionVector(v2, u1);
		//Normalize v2
		Vector3d u2 = createNormalizedVector(v2);
		
		// u3
		Vector3d v3 = new Vector3d(a3);
		removeOrthogonalProjectionVector(v3, u1);
		removeOrthogonalProjectionVector(v3, u2);
		Vector3d u3 = createNormalizedVector(v3);
		
		return new Vector3d[] {
				u1, u2, u3
		};
	}
	
	/**
	 *Get the unit vector of vector a.
	 * @param a vector a
	 * @return normalized vector
	 */
	private static Vector3d createNormalizedVector(Vector3d a) {
		Vector3d ret = new Vector3d(a);
		ret.normalize();
		return ret;
	}
	
	/**
	 *Get the normal projection vector of the vector a in the v direction.
	 * @param a vector a
	 * @param u Unit vector of vector v
	 */
	private static Vector3d createOrthogonalProjectionVector(
			Vector3d a,
			Vector3d u) {
		Vector3d ret = new Vector3d(u);
		ret.scale( u.dot(a) );
		return ret;
	}
	
	
	/**
	 *Remove the orthodox projection component of vector v from vector a
	 * @param a vector a
	 * @param u Unit vector of vector v
	 */
	private static void removeOrthogonalProjectionVector(
			Vector3d a,
			Vector3d u) {
		Vector3d orthoProj = createOrthogonalProjectionVector(a, u);
		a.sub(orthoProj);
	}
	

}


Test code.

package hoge.piyo;

import javax.vecmath.Vector3d;
import org.junit.Test;

public class LinearAlgebraUtilTest {
	
	
	@Test
	public void testCreateOrthonormalBasis() throws Exception {
		
		//check the answer.
		{
			//Simple example
			Vector3d[] S = new Vector3d[] {
					new Vector3d(0, 0, 10),
					new Vector3d(10, 0, 0),
					new Vector3d(0, 20, 0)
			};
			Vector3d[] T = LinearAlgebraUtil.createOrthonormalBasis(S[0], S[1], S[2]);
			dumpResult(S, T);
		}
		
		{
			//Simple example 2
			Vector3d[] S = new Vector3d[] {
					new Vector3d(0, 0, 10),
					new Vector3d(10, 10, 0),
					new Vector3d(5, 20, 0)
			};
			Vector3d[] T = LinearAlgebraUtil.createOrthonormalBasis(S[0], S[1], S[2]);
			dumpResult(S, T);
		}
		
		//Excerpt of calculation result sample from the result searched by orthonormal basis example
		
		{
			// http://www.math4all.in/public_html/linear%20algebra/chapter8.2.html
			// 8.2.5 Examples:
			Vector3d[] S = new Vector3d[] {
					new Vector3d(1, 1, 1),
					new Vector3d(-1, 0, -1),
					new Vector3d(-1, 2, 3)
			};
			Vector3d[] T = LinearAlgebraUtil.createOrthonormalBasis(S[0], S[1], S[2]);
			dumpResult(S, T);
		}

		{
			// http://lyle.smu.edu/emis/8371/book/chap3/node12.html
			// Examples:
			Vector3d[] S = new Vector3d[] {
					new Vector3d(1, 2, 2),
					new Vector3d(1, 1, 0),
					new Vector3d(1, -1, 1)
			};
			Vector3d[] T = LinearAlgebraUtil.createOrthonormalBasis(S[0], S[1], S[2]);
			dumpResult(S, T);
		}
		
		{
			// http://www.mcu.edu.tw/department/management/stat/ch_web/etea/linear/CH6.8%20--%206.9%20Orthonormal%20Bases%20in%20R%5En.pdf
			// Example p6 - p12
			// ->Since the answer here is orthogonal, it is necessary to normalize and think about it.
			Vector3d[] S = new Vector3d[] {
					new Vector3d(1, 0, 0),
					new Vector3d(1, 2, 0),
					new Vector3d(0, 0, 3)
			};
			Vector3d[] T = LinearAlgebraUtil.createOrthonormalBasis(S[0], S[1], S[2]);
			dumpResult(S, T);
		}
		
	}
	
	private static void dumpResult(Vector3d[] S, Vector3d[] T) {
		System.out.println(String.format("S:%s", toString(S)));
		System.out.println(String.format("T:%s", toString(T)));
		System.out.println();
	}
	
	private static String toString(Vector3d[] vs) {
		StringBuilder sb = new StringBuilder();
		for (Vector3d v : vs) {
			sb.append(String.format("(%f, %f, %f) ", v.x, v.y, v.z)).append(" ");
		}
		return sb.toString();
	}
}

Test code output result

S:(0.000000, 0.000000, 10.000000)  (10.000000, 0.000000, 0.000000)  (0.000000, 20.000000, 0.000000)  
T:(0.000000, 0.000000, 1.000000)  (1.000000, 0.000000, 0.000000)  (0.000000, 1.000000, 0.000000)  

S:(0.000000, 0.000000, 10.000000)  (10.000000, 10.000000, 0.000000)  (5.000000, 20.000000, 0.000000)  
T:(0.000000, 0.000000, 1.000000)  (0.707107, 0.707107, 0.000000)  (-0.707107, 0.707107, 0.000000)  

S:(1.000000, 1.000000, 1.000000)  (-1.000000, 0.000000, -1.000000)  (-1.000000, 2.000000, 3.000000)  
T:(0.577350, 0.577350, 0.577350)  (-0.408248, 0.816497, -0.408248)  (-0.707107, -0.000000, 0.707107)  

S:(1.000000, 2.000000, 2.000000)  (1.000000, 1.000000, 0.000000)  (1.000000, -1.000000, 1.000000)  
T:(0.333333, 0.666667, 0.666667)  (0.666667, 0.333333, -0.666667)  (0.666667, -0.666667, 0.333333)  

S:(1.000000, 0.000000, 0.000000)  (1.000000, 2.000000, 0.000000)  (0.000000, 0.000000, 3.000000)  
T:(1.000000, 0.000000, 0.000000)  (0.000000, 1.000000, 0.000000)  (0.000000, 0.000000, 1.000000)  

Recommended Posts

Source code for finding an orthonormal basis with the Gram-Schmidt orthogonalization method
Code for solving a random number matrix with the Pivot Gauss elimination method
Sample source code for finding the least common multiple of multiple values in Java
Finding pi with the Monte Carlo method? (Ruby)
Rewrite the code for java.io.File with java.nio.Path and java.nio.Files
Specify the character code of the source when building with Maven
[Java] How to search for a value in an array (or list) with the contains method
Oracle Live for the Code
When reading the source code
Use an example domain for the package name in the sample code
Let's experience the authorization code grant flow with Spring Security OAuth-Part 2: Creating an app for the time being