Problem

You have a number of linear equations (that is, equations that look like "2x + 10y + 8z = 54"), and you want to figure out the solution: the values of x, y, and z. You have as many equations as you have variables, so you can be certain of a unique solution.

Solution

Create two `Matrix` objects. The first `Matrix` should contain the coefficients of your equations (the 2, 10, and 8 of "2x + 10y + 8z = 54"), and the second should contain the constant results (the 54 of the same equation). The numbers in both matrices should be represented as floating-point numbers, rational numbers, or `BigDecimal` objects: anything other than plain Ruby integers.

Then invert the coefficient matrix with ` Matrix#inverse`, and multiply the result by the matrix full of constants. The result will be a third `Matrix` containing the solutions to your equations.

For instance, consider these three linear equations in three variables:

2x + 10y + 8z = 54 7y + 4z = 30 5x + 5y + 5z = 35

To solve these equations, create the two matrices:

require 'matrix' require 'rational' coefficients = [[2, 10, 8], [0, 7, 4], [5, 5, 5]].collect! do |row| row.collect! { |x| Rational(x) } end coefficients = Matrix[*coefficients] # => Matrix[[Rational(2, 1), Rational(10, 1), Rational(8, 1)], # => [Rational(0, 1), Rational(7, 1), Rational(4, 1)], # => [Rational(5, 1), Rational(5, 1), Rational(5, 1)]] constants = Matrix[[Rational(54)], [Rational(30)], [Rational(35)]]

Take the inverse of the coefficient matrix, and multiply it by the results matrix. The result will be a matrix containing the values for your variables.

solutions = coefficients.inverse * constants # => Matrix[[Rational(1, 1)], [Rational(2, 1)], [Rational(4, 1)]]

This means that, in terms of the original equations, x=1, y=2, and z=4.

Discussion

This may seem like magic, but it's analagous to how you might use algebra to solve a single equation in a single variable. Such an equation looks something like Ax = B: for instance, 6x = 18. To solve for x, you divide both sides by the coefficient:

The sixes on the left side of the equation cancel out, and you can show that x is 18/6, or 3.

In that case there's only one coefficient and one constant. With n equations in n variables, you have n2 coefficients and n constants, but by packing them into matrices you can solve the problem in the same way.

Here's a side-by-side comparision of the set of equations from the Solution, and the corresponding matrices created in order to solve the system of equations.

2x + 10y + 8z = 54 | [ 2 10 8] [x] [54] x + 7y + 4z = 31 | [ 1 7 4] [y] = [31] 5x + 5y + 5z = 35 | [ 5 5 5] [z] [35]

If you think of each matrix as a single value, this looks exactly like an equation in a single variable. It's Ax = B, only this time A, x, and B are matrices. Again you can solve the problem by dividing both sides by A: x = B/A. This time, you'll use matrix division instead of scalar division, and your result will be a matrix of solutions instead of a single solution.

For numbers, dividing B by A is equivalent to multiplying B by the inverse of A. For instance, 9/3 equals 9 * 1/3. The same is true of matrices. To divide a matrix B by another matrix A, you multiply B by the inverse of A.

The `Matrix` class overloads the division operator to do multiplication by the inverse, so you might wonder why we don't just use that. The problem is that `Matrix#/` calculates B/A as `B*A.inverse`, and what we want is `A.inverse*B`. Matrix multiplication isn't commutative, and so neither is division. The developers of the `Matrix` class had to pick an order to do the multiplication, and they chose the one that won't work for solving a system of equations.

For the most accurate results, you should use `Rational` or `BigDecimal` numbers to represent your coefficients and values. You should never use integers. Calling `Matrix#inverse` on a matrix full of integers will do the inversion using integer division. The result will be totally inaccurate, and you won't get the right solutions to your equations.

Here's a demonstration of the problem. Multiplying a matrix by its inverse should get you an identity matrix, full of zeros but with ones going down the right diagonal. This is analagous to the way multiplying 3 by 1/3 gets you 1.

When the matrix is full of rational numbers, this works fine:

matrix = Matrix[[Rational(1), Rational(2)], [Rational(2), Rational(1)]] matrix.inverse # => Matrix[[Rational(-1, 3), Rational(2, 3)], # => [Rational(2, 3), Rational(-1, 3)]] matrix * matrix.inverse # => Matrix[[Rational(1, 1), Rational(0, 1)], # => [Rational(0, 1), Rational(1, 1)]]

But if the matrix is full of integers, multiplying it by its inverse will give you a matrix that looks nothing like an identity matrix.

matrix = Matrix[[1, 2], [2, 1]] matrix.inverse # => Matrix[[-1, 1], # => [0, -1]] matrix * matrix.inverse # => Matrix[[-1, -1], # => [-2, 1]]

Inverting a matrix that contains floating-point numbers is a lesser mistake: `Matrix#inverse` tends to magnify the inevitable floating-point rounding errors. Multiplying a matrix full of floating-point numbers by its inverse will get you a matrix that's almost, but not quite, an identity matrix.

float_matrix = Matrix[[1.0, 2.0], [2.0, 1.0]] float_matrix.inverse # => Matrix[[-0.333333333333333, 0.666666666666667], # => [0.666666666666667, -0.333333333333333]] float_matrix * float_matrix.inverse # => Matrix[[1.0, 0.0], # => [1.11022302462516e-16, 1.0]]

See Also

- Recipe 2.10, "Multiplying Matrices"
- Another way of solving systems of linear equations is with Gauss-Jordan elimination; Shin-ichiro Hara has written an
`algebra`library for Ruby, which includes a module for doing Gaussian elimination, along with lots of other linear algebra libraries (http://blade.nagaokaut.ac.jp/~sinara/ruby/math/algebra/) - There is also a package, called
`linalg`, which provides Ruby bindings to the C/Fortran LAPACK library for linear algebra (http://rubyforge.org/projects/linalg/)

Strings

- Strings
- Building a String from Parts
- Substituting Variables into Strings
- Substituting Variables into an Existing String
- Reversing a String by Words or Characters
- Representing Unprintable Characters
- Converting Between Characters and Values
- Converting Between Strings and Symbols
- Processing a String One Character at a Time
- Processing a String One Word at a Time
- Changing the Case of a String
- Managing Whitespace
- Testing Whether an Object Is String-Like
- Getting the Parts of a String You Want
- Handling International Encodings
- Word-Wrapping Lines of Text
- Generating a Succession of Strings
- Matching Strings with Regular Expressions
- Replacing Multiple Patterns in a Single Pass
- Validating an Email Address
- Classifying Text with a Bayesian Analyzer

Numbers

- Numbers
- Parsing a Number from a String
- Comparing Floating-Point Numbers
- Representing Numbers to Arbitrary Precision
- Representing Rational Numbers
- Generating Random Numbers
- Converting Between Numeric Bases
- Taking Logarithms
- Finding Mean, Median, and Mode
- Converting Between Degrees and Radians
- Multiplying Matrices
- Solving a System of Linear Equations
- Using Complex Numbers
- Simulating a Subclass of Fixnum
- Doing Math with Roman Numbers
- Generating a Sequence of Numbers
- Generating Prime Numbers
- Checking a Credit Card Checksum

Date and Time

- Date and Time
- Finding Todays Date
- Parsing Dates, Precisely or Fuzzily
- Printing a Date
- Iterating Over Dates
- Doing Date Arithmetic
- Counting the Days Since an Arbitrary Date
- Converting Between Time Zones
- Checking Whether Daylight Saving Time Is in Effect
- Converting Between Time and DateTime Objects
- Finding the Day of the Week
- Handling Commercial Dates
- Running a Code Block Periodically
- Waiting a Certain Amount of Time
- Adding a Timeout to a Long-Running Operation

Arrays

- Arrays
- Iterating Over an Array
- Rearranging Values Without Using Temporary Variables
- Stripping Duplicate Elements from an Array
- Reversing an Array
- Sorting an Array
- Ignoring Case When Sorting Strings
- Making Sure a Sorted Array Stays Sorted
- Summing the Items of an Array
- Sorting an Array by Frequency of Appearance
- Shuffling an Array
- Getting the N Smallest Items of an Array
- Building Up a Hash Using Injection
- Extracting Portions of Arrays
- Computing Set Operations on Arrays
- Partitioning or Classifying a Set

Hashes

- Hashes
- Using Symbols as Hash Keys
- Creating a Hash with a Default Value
- Adding Elements to a Hash
- Removing Elements from a Hash
- Using an Array or Other Modifiable Object as a Hash Key
- Keeping Multiple Values for the Same Hash Key
- Iterating Over a Hash
- Iterating Over a Hash in Insertion Order
- Printing a Hash
- Inverting a Hash
- Choosing Randomly from a Weighted List
- Building a Histogram
- Remapping the Keys and Values of a Hash
- Extracting Portions of Hashes
- Searching a Hash with Regular Expressions

Files and Directories

- Files and Directories
- Checking to See If a File Exists
- Checking Your Access to a File
- Changing the Permissions on a File
- Seeing When a File Was Last Used Problem
- Listing a Directory
- Reading the Contents of a File
- Writing to a File
- Writing to a Temporary File
- Picking a Random Line from a File
- Comparing Two Files
- Performing Random Access on Read-Once Input Streams
- Walking a Directory Tree
- Locking a File
- Backing Up to Versioned Filenames
- Pretending a String Is a File
- Redirecting Standard Input or Output
- Processing a Binary File
- Deleting a File
- Truncating a File
- Finding the Files You Want
- Finding and Changing the Current Working Directory

Code Blocks and Iteration

- Code Blocks and Iteration
- Creating and Invoking a Block
- Writing a Method That Accepts a Block
- Binding a Block Argument to a Variable
- Blocks as Closures: Using Outside Variables Within a Code Block
- Writing an Iterator Over a Data Structure
- Changing the Way an Object Iterates
- Writing Block Methods That Classify or Collect
- Stopping an Iteration
- Looping Through Multiple Iterables in Parallel
- Hiding Setup and Cleanup in a Block Method
- Coupling Systems Loosely with Callbacks

Objects and Classes8

- Objects and Classes8
- Managing Instance Data
- Managing Class Data
- Checking Class or Module Membership
- Writing an Inherited Class
- Overloading Methods
- Validating and Modifying Attribute Values
- Defining a Virtual Attribute
- Delegating Method Calls to Another Object
- Converting and Coercing Objects to Different Types
- Getting a Human-Readable Printout of Any Object
- Accepting or Passing a Variable Number of Arguments
- Simulating Keyword Arguments
- Calling a Superclasss Method
- Creating an Abstract Method
- Freezing an Object to Prevent Changes
- Making a Copy of an Object
- Declaring Constants
- Implementing Class and Singleton Methods
- Controlling Access by Making Methods Private

Modules and Namespaces

- Modules and Namespaces
- Simulating Multiple Inheritance with Mixins
- Extending Specific Objects with Modules
- Mixing in Class Methods
- Implementing Enumerable: Write One Method, Get 22 Free
- Avoiding Naming Collisions with Namespaces
- Automatically Loading Libraries as Needed
- Including Namespaces
- Initializing Instance Variables Defined by a Module
- Automatically Initializing Mixed-In Modules

Reflection and Metaprogramming

- Reflection and Metaprogramming
- Finding an Objects Class and Superclass
- Listing an Objects Methods
- Listing Methods Unique to an Object
- Getting a Reference to a Method
- Fixing Bugs in Someone Elses Class
- Listening for Changes to a Class
- Checking Whether an Object Has Necessary Attributes
- Responding to Calls to Undefined Methods
- Automatically Initializing Instance Variables
- Avoiding Boilerplate Code with Metaprogramming
- Metaprogramming with String Evaluations
- Evaluating Code in an Earlier Context
- Undefining a Method
- Aliasing Methods
- Doing Aspect-Oriented Programming
- Enforcing Software Contracts

XML and HTML

- XML and HTML
- Checking XML Well-Formedness
- Extracting Data from a Documents Tree Structure
- Extracting Data While Parsing a Document
- Navigating a Document with XPath
- Parsing Invalid Markup
- Converting an XML Document into a Hash
- Validating an XML Document
- Substituting XML Entities
- Creating and Modifying XML Documents
- Compressing Whitespace in an XML Document
- Guessing a Documents Encoding
- Converting from One Encoding to Another
- Extracting All the URLs from an HTML Document
- Transforming Plain Text to HTML
- Converting HTML Documents from the Web into Text
- A Simple Feed Aggregator

Graphics and Other File Formats

- Graphics and Other File Formats
- Thumbnailing Images
- Adding Text to an Image
- Converting One Image Format to Another
- Graphing Data
- Adding Graphical Context with Sparklines
- Strongly Encrypting Data
- Parsing Comma-Separated Data
- Parsing Not-Quite-Comma-Separated Data
- Generating and Parsing Excel Spreadsheets
- Compressing and Archiving Files with Gzip and Tar
- Reading and Writing ZIP Files
- Reading and Writing Configuration Files
- Generating PDF Files
- Representing Data as MIDI Music

Databases and Persistence

- Databases and Persistence
- Serializing Data with YAML
- Serializing Data with Marshal
- Persisting Objects with Madeleine
- Indexing Unstructured Text with SimpleSearch
- Indexing Structured Text with Ferret
- Using Berkeley DB Databases
- Controlling MySQL on Unix
- Finding the Number of Rows Returned by a Query
- Talking Directly to a MySQL Database
- Talking Directly to a PostgreSQL Database
- Using Object Relational Mapping with ActiveRecord
- Using Object Relational Mapping with Og
- Building Queries Programmatically
- Validating Data with ActiveRecord
- Preventing SQL Injection Attacks
- Using Transactions in ActiveRecord
- Adding Hooks to Table Events
- Adding Taggability with a Database Mixin

Internet Services

- Internet Services
- Grabbing the Contents of a Web Page
- Making an HTTPS Web Request
- Customizing HTTP Request Headers
- Performing DNS Queries
- Sending Mail
- Reading Mail with IMAP
- Reading Mail with POP3
- Being an FTP Client
- Being a Telnet Client
- Being an SSH Client
- Copying a File to Another Machine
- Being a BitTorrent Client
- Pinging a Machine
- Writing an Internet Server
- Parsing URLs
- Writing a CGI Script
- Setting Cookies and Other HTTP Response Headers
- Handling File Uploads via CGI
- Running Servlets with WEBrick
- A Real-World HTTP Client

Web Development Ruby on Rails

- Web Development Ruby on Rails
- Writing a Simple Rails Application to Show System Status
- Passing Data from the Controller to the View
- Creating a Layout for Your Header and Footer
- Redirecting to a Different Location
- Displaying Templates with Render
- Integrating a Database with Your Rails Application
- Understanding Pluralization Rules
- Creating a Login System
- Storing Hashed User Passwords in the Database
- Escaping HTML and JavaScript for Display
- Setting and Retrieving Session Information
- Setting and Retrieving Cookies
- Extracting Code into Helper Functions
- Refactoring the View into Partial Snippets of Views
- Adding DHTML Effects with script.aculo.us
- Generating Forms for Manipulating Model Objects
- Creating an Ajax Form
- Exposing Web Services on Your Web Site
- Sending Mail with Rails
- Automatically Sending Error Messages to Your Email
- Documenting Your Web Site
- Unit Testing Your Web Site
- Using breakpoint in Your Web Application

Web Services and Distributed Programming

- Web Services and Distributed Programming
- Searching for Books on Amazon
- Finding Photos on Flickr
- Writing an XML-RPC Client
- Writing a SOAP Client
- Writing a SOAP Server
- Searching the Web with Googles SOAP Service
- Using a WSDL File to Make SOAP Calls Easier
- Charging a Credit Card
- Finding the Cost to Ship Packages via UPS or FedEx
- Sharing a Hash Between Any Number of Computers
- Implementing a Distributed Queue
- Creating a Shared Whiteboard
- Securing DRb Services with Access Control Lists
- Automatically Discovering DRb Services with Rinda
- Proxying Objects That Cant Be Distributed
- Storing Data on Distributed RAM with MemCached
- Caching Expensive Results with MemCached
- A Remote-Controlled Jukebox

Testing, Debugging, Optimizing, and Documenting

- Testing, Debugging, Optimizing, and Documenting
- Running Code Only in Debug Mode
- Raising an Exception
- Handling an Exception
- Rerunning After an Exception
- Adding Logging to Your Application
- Creating and Understanding Tracebacks
- Writing Unit Tests
- Running Unit Tests
- Testing Code That Uses External Resources
- Using breakpoint to Inspect and Change the State of Your Application
- Documenting Your Application
- Profiling Your Application
- Benchmarking Competing Solutions
- Running Multiple Analysis Tools at Once
- Who s Calling That Method? A Call Graph Analyzer

Packaging and Distributing Software

- Packaging and Distributing Software
- Finding Libraries by Querying Gem Respositories
- Installing and Using a Gem
- Requiring a Specific Version of a Gem
- Uninstalling a Gem
- Reading Documentation for Installed Gems
- Packaging Your Code as a Gem
- Distributing Your Gems
- Installing and Creating Standalone Packages with setup.rb

Automating Tasks with Rake

- Automating Tasks with Rake
- Automatically Running Unit Tests
- Automatically Generating Documentation
- Cleaning Up Generated Files
- Automatically Building a Gem
- Gathering Statistics About Your Code
- Publishing Your Documentation
- Running Multiple Tasks in Parallel
- A Generic Project Rakefile

Multitasking and Multithreading

- Multitasking and Multithreading
- Running a Daemon Process on Unix
- Creating a Windows Service
- Doing Two Things at Once with Threads
- Synchronizing Access to an Object
- Terminating a Thread
- Running a Code Block on Many Objects Simultaneously
- Limiting Multithreading with a Thread Pool
- Driving an External Process with popen
- Capturing the Output and Error Streams from a Unix Shell Command
- Controlling a Process on Another Machine
- Avoiding Deadlock

User Interface

- User Interface
- Getting Input One Line at a Time
- Getting Input One Character at a Time
- Parsing Command-Line Arguments
- Testing Whether a Program Is Running Interactively
- Setting Up and Tearing Down a Curses Program
- Clearing the Screen
- Determining Terminal Size
- Changing Text Color
- Reading a Password
- Allowing Input Editing with Readline
- Making Your Keyboard Lights Blink
- Creating a GUI Application with Tk
- Creating a GUI Application with wxRuby
- Creating a GUI Application with Ruby/GTK
- Creating a Mac OS X Application with RubyCocoa
- Using AppleScript to Get User Input

Extending Ruby with Other Languages

- Extending Ruby with Other Languages
- Writing a C Extension for Ruby
- Using a C Library from Ruby
- Calling a C Library Through SWIG
- Writing Inline C in Your Ruby Code
- Using Java Libraries with JRuby

System Administration

- System Administration
- Scripting an External Program
- Managing Windows Services
- Running Code as Another User
- Running Periodic Tasks Without cron or at
- Deleting Files That Match a Regular Expression
- Renaming Files in Bulk
- Finding Duplicate Files
- Automating Backups
- Normalizing Ownership and Permissions in User Directories
- Killing All Processes for a Given User

Ruby Cookbook (Cookbooks (OReilly))

ISBN: 0596523696

EAN: 2147483647

EAN: 2147483647

Year: N/A

Pages: 399

Pages: 399

Authors: Lucas Carlson, Leonard Richardson

Similar book on Amazon

Flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net